Most array interview questions are one of four patterns. Recognising which is the whole game.
Two pointers
Two indices moving through the array, often from opposite ends.
Use when the array is sorted or can be sorted, and you are looking for a pair or triple satisfying a condition.
Find two numbers summing to a target in a sorted array: start at both ends. If the sum is too large, move the right pointer left; too small, move the left pointer right. O(n) instead of O(n^2).
Sliding window
A contiguous range that expands and contracts.
Use for contiguous subarray problems: longest substring without repeats, minimum window containing a set, maximum sum of k consecutive elements.
The pattern: expand the right edge until the window is invalid, then contract the left edge until it is valid again. Each element enters and leaves once, so O(n).
Hash map for lookup
Trade space for time. The archetype is two-sum on an unsorted array: store each value's index as you go, and check whether the complement has already been seen. One pass, O(n) time, O(n) space.
Whenever you find yourself writing a nested loop to search for something, ask whether a hash map removes the inner loop.
Prefix sums
Precompute cumulative sums so any range sum is a subtraction. O(n) preprocessing, O(1) per query.
Extends to 2D grids, and the same idea with XOR or products solves several variants. Combined with a hash map it answers "how many subarrays sum to k" in linear time.
Choosing between them
- Sorted, looking for pairs → two pointers.
- Contiguous range with a constraint → sliding window.
- Unsorted, need to find whether something exists → hash map.
- Repeated range queries → prefix sums.
The edge cases to state
Empty array, single element, all identical values, negative numbers (which break some sliding-window assumptions), and integer overflow on sums. Naming these unprompted is scored.
Practise in programming and DSA.