Array
A contiguous block of memory with O(1) random access by index.
Properties
- Random access: O(1)
- Search (unsorted): O(n)
- Search (sorted): O(log n) with Binary Search
- Insert/delete at end: O(1) amortized
- Insert/delete at arbitrary index: O(n)
Common Techniques
- Prefix sums: precompute
prefix[i] = sum(arr[0..i])for O(1) range sum queries - Sorting first: many problems become easier on a sorted array (Two Pointers, Binary Search, Greedy)
- Two pointers: works in-place without extra space
- Sliding window: optimal for contiguous subarray problems
Prefix Sum Template
prefix = [0] * (len(arr) + 1)
for i, val in enumerate(arr):
prefix[i + 1] = prefix[i] + val
# Sum of arr[l..r] (inclusive)
range_sum = prefix[r + 1] - prefix[l]