Arrays, Strings, Hashing and Two Pointers
Arrays give O(1) indexing and hash tables give O(1) average lookups; most array interview problems reduce to a hash map, two pointers, a sliding window or prefix sums.
Key points
- 1
Array access is base + i × size, so indexing is O(1) and inserting in the middle is O(n); dynamic arrays grow geometrically for amortized O(1) appends.
- 2
Hash tables are O(1) on average and O(n) in the worst case; resizing keeps the load factor bounded, and open addressing needs tombstones on delete.
- 3
Keys must be hashable and must not change while stored, or lookups miss them.
- 4
Two pointers need a monotonic structure such as a sorted array; a sliding window needs a monotonic constraint (positive sums, distinct counts).
- 5
For exact subarray sums, especially with negatives, use prefix sums with a hash map seeded with {0: 1}.
- 6
Kadane, Boyer–Moore, cyclic placement and the reversal trick each solve a classic problem in O(n) time and O(1) space.
Common traps
Kadane initialised with 0 returns 0 for all-negative input.
Sliding-window shrinking must be a while loop, and the start pointer must never move backwards.
Boyer–Moore always returns a candidate; verify it when a majority is not guaranteed.
Read the source
Test yourself on Arrays, Strings, Hashing and Two Pointers
Ten questions, with the answer and explanation after each one.