Array Patterns
Arrays are where most interview questions start, and where most of the reusable ideas live. Almost every array problem is one of a small number of shapes: a window that slides, two indices that converge, a running total you can subtract, or a search space you can halve. Learning to recognise the shape is worth far more than memorising individual problems, because the same four shapes reappear in strings, matrices and linked lists.
Where to start, and what comes next
- 01
Two Pointer
The simplest place to see two indices doing the work of a nested loop. Start here because the idea underpins the window as well.
- 02
Sliding Window
A special case of two pointers where the region between them is the answer. Fixed size first, then variable, which is where the grow-and-shrink discipline appears.
- 03
Prefix Sum
The answer to every range-sum question, and paired with a hash map it handles subarray sums that a window cannot, including negatives.
- 04
Kadane's / Subarray
The first genuinely dynamic-programming idea, disguised as an array scan. Worth doing before the DP topic.
- 05
Binary Search
Not just for finding values. The boundary variant generalises to any yes-or-no condition that flips once, which is what binary searching the answer means.
- 06
Intervals
Sorting turns overlap questions into a single pass. The same sort-then-scan shape carries straight into greedy.
- 07
Cyclic Sort
A narrow trick with a big payoff on the family of problems about numbers in a known range, where it removes the need for extra space entirely.
- 08
Arrays Utility API
The Java API you will actually type. Worth a read once so that copyOfRange bounds and binarySearch return values do not surprise you under time pressure.
If you only have time for three things
- Sliding window, both fixed and variable size. More interview questions reduce to this than to anything else on the list.
- Prefix sums with a hash map, which is the escape hatch when a window fails because of negative numbers.
- Binary search on a condition rather than a value, since that is the version that shows up in hard problems.
The array round is usually checking whether you can get from a brute-force O(n squared) to O(n) and say why the improvement is valid. Stating the brute force first is not a weakness, it is the baseline you then beat. What loses points is jumping to a window without checking that the problem is actually contiguous, or using one on input with negative numbers where the shrink step is unsound.
The idea underneath
When you see 'subarray', 'contiguous', or 'in-place', think arrays. The key is reducing brute-force O(n²) to O(n) using sliding window, two pointers, or prefix sums.
Problems that use these patterns
Head to head
Questions people ask
How do I recognise a sliding window problem?
Look for a contiguous requirement and an optimisation together: subarray or substring, alongside longest, shortest, or at most k. If the answer is allowed to skip elements it is not a window, and you probably want dynamic programming.
When does two pointers need a sorted array?
When the pointers converge from both ends, as in two sum on sorted input. The movement rule relies on knowing that moving left decreases and moving right increases, which is only true when sorted. Fast and slow pointers need no ordering at all.
What is the difference between prefix sums and a sliding window?
A window assumes shrinking from the left only ever reduces the total, which negatives break. Prefix sums make no such assumption, so subarray-sum problems with negative numbers use a running total and a hash map of previously seen totals.