Back to Topics
Arrays
An array is a contiguous block of memory storing elements of the same type. It is the most fundamental data structure and the backbone of many algorithms. Random access in O(1) makes arrays ideal for index-based lookups, but insertions and deletions in the middle are costly.
Key Ideas
- Zero-indexed contiguous memory — element i lives at base + i × size
- Random access in O(1) by index; linear search O(n) without sorting
- Insertion or deletion at an arbitrary position shifts all following elements → O(n)
- Amortized O(1) append to a dynamic array (e.g. Python list, Java ArrayList)
- Two-pointer and sliding-window patterns eliminate nested loops for many subarray problems
- Prefix sums precompute cumulative totals to answer range queries in O(1)
Complexity
| Operation | Time | Space |
|---|---|---|
| Access by index | O(1) | O(1) |
| Search (unsorted) | O(n) | O(1) |
| Insert at end | O(1)* | O(1) |
| Insert at middle | O(n) | O(1) |
| Delete at end | O(1) | O(1) |
| Delete at middle | O(n) | O(1) |
Common Patterns
Two PointersLeft and right pointers converge inward — useful for sorted arrays, pair sums, and in-place reversals.
Sliding WindowExpand/shrink a window of elements to track a running aggregate — avoids re-computation over subarrays.
Prefix SumPrecompute cumulative sums so any subarray sum [i, j] = prefix[j] − prefix[i−1] in O(1).
Kadane's AlgorithmTrack the maximum subarray sum ending at each index; update global max in one pass.
Code Example
Two-pointer: reverse array in-placepython
def reverse(arr: list[int]) -> None:
left, right = 0, len(arr) - 1
while left < right:
arr[left], arr[right] = arr[right], arr[left]
left += 1
right -= 1💡
When you see 'subarray' or 'contiguous', reach for sliding window or prefix sums before thinking O(n²).