What is an array in data structures?
An array is a fundamental data structure that stores a fixed-size sequential collection of elements of the same type in contiguous memory locations, allowing constant-time access by index.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Static vs Dynamic Arrays
-
Static array: Size fixed at allocation; cannot grow or shrink. Languages like C, C++, Java (primitive arrays) use this model.
-
Dynamic array: Resizes automatically when capacity is exceeded (e.g., Python
list, C++std::vector, JavaArrayList). Growth typically doubles capacity, making append amortized O(1). -
Python
listis a dynamic array of object references; the underlying buffer holds pointers, not the objects themselves.
Memory Layout and Access
-
Elements stored contiguously: address of element
i=base_address + i * element_size. -
Index access O(1): direct address calculation, no traversal.
-
Cache-friendly: sequential access exploits spatial locality.
-
Homogeneous type (in static arrays): each slot same size; dynamic arrays of references can hold any object type.
Common Operations and Complexities
| Operation | Static Array | Dynamic Array (append at end) | Dynamic Array (insert/delete middle) |
|---|---|---|---|
| Access by index | O(1) | O(1) | O(1) |
| Search (unsorted) | O(n) | O(n) | O(n) |
| Insert at end | N/A (fixed size) | Amortized O(1) | O(n) |
| Delete at end | N/A | O(1) | O(n) |
Insert/delete at index i |
N/A | O(n - i) | O(n - i) |
| Space | O(n) | O(n) (capacity ≥ size) | O(n) |
Reasoning: Insert/delete in middle shifts all subsequent elements; dynamic array resize copies entire buffer (amortized cost spread over many appends).
Typical Array Patterns
-
Two pointers: left/right indices moving toward center (e.g., two-sum on sorted array, palindrome check).
-
Sliding window: maintain a subarray
[left, right)satisfying a condition; expand right, contract left. -
Prefix sums: precompute
prefix[i] = sum(arr[:i])for O(1) range-sum queries. -
Kadane’s algorithm: maximum subarray sum in O(n) time, O(1) space.
-
In-place swaps / cyclic sort: place each value at its correct index (for permutations 1..n).
-
Dutch national flag: three-way partition around a pivot (used in quicksort, sort colors).
Common Pitfalls
-
Off-by-one errors: loop bounds
range(len(arr))vsrange(len(arr) - 1); inclusive vs exclusive endpoints. -
Mutating input unintentionally: many interview problems allow in-place modification, but confirm with interviewer.
-
Confusing Python
listwith linked list:list.pop(0)andlist.insert(0, x)are O(n); usecollections.dequefor queue operations. -
Shared-row bug in 2D arrays:
[[0] * n] * mcreatesmreferences to the same row; use[[0] * n for _ in range(m)]. -
Assuming dynamic array append is always O(1): it is amortized; a single append that triggers resize takes O(n).
-
Interview follow-ups: “How would you implement a dynamic array from scratch?” “When would you choose a linked list over an array?” “How does memory fragmentation affect large arrays?”