Synthesis: which pattern to use?
You know the 5 patterns. What's left is the skill that wins the interview: glancing at a new statement and knowing which one to use — with a justification.
The section's decision tree
Faced with an array problem, run through these questions in order:
1. Is the question about a CONTIGUOUS SLICE (subarray)?
├── Yes, and the values are all positive (or fixed-size window)
│ → SLIDING WINDOW (state enters/leaves through the edges)
├── Yes, but there are NEGATIVES
│ ├── "largest sum/product" → KADANE (extend or restart)
│ └── "how many sum to k" /
│ range questions → PREFIX (+ hash map to count)
└── No, continue ↓
2. Am I looking for PAIRS/TRIPLES of elements?
├── I need EXACT values (complement) and/or the original indices
│ → HASH MAP (ask the past, record for the future)
└── Sorted array (or I can sort) / INEQUALITY condition
→ TWO POINTERS (proven bulk discard)
3. Do I repeatedly ask "have I seen it? how many times? does it exist?"
→ HASH MAP
4. "For each position, something about ALL the rest" (left × right)
→ PREFIX + SUFFIX (two passes)
And the final sanity check, always: the limits. n up to 10⁵-10⁶ asks for O(n) or O(n log n) — if your plan is O(n²), go back to the tree.
The complete map of the section
| Pattern | Waste it eliminates | Key question | Time | Space |
|---|---|---|---|---|
| Hash map | repeated searching | "have I seen what I'm looking for?" | O(n) | O(n) |
| Two pointers | pairs with no chance | "which side do I abandon — and why?" | O(n)* | O(1) |
| Sliding window | recomputing windows | "what enters, what leaves?" | O(n) | O(1)** |
| Prefix/Suffix | re-summing slices | "can I pre-accumulate?" | O(n) | O(1)-O(n) |
| Kadane | re-evaluating every start | "do I extend or restart?" | O(n) | O(1) |
* + O(n log n) if you need to sort first. ** depends on the window's state (a scalar = O(1); a count map = O(k)).
Notice what they all have in common: one pass (or two) with O(1) work per element, each with its own trick to never revisit work already done. That's the spirit of everything that defeats O(n²).
Section quiz
The real test: statements you haven't seen in the lessons. For each one, identify the pattern — and, more importantly, be able to say why. 7+ correct: you're ready for the final exam.
🧠 Section quiz: Array
0/101. 'Given an array and k, return the LARGEST AVERAGE among all subarrays of exactly k elements.' Which pattern?
2. 'In a SORTED array, find two numbers whose sum is CLOSEST to zero.' Which pattern and why?
3. 'Count how many contiguous subarrays sum to exactly k. The array has NEGATIVE numbers.' Which pattern?
4. 'Find the contiguous subarray with the largest sum' (with negatives). Which pattern?
5. 'For each position i, return the SUM of all elements except nums[i].' Which O(n) approach?
6. 'Check whether some pair of EQUAL elements is at most k positions apart.' Which pattern?
7. Your solution is O(n²) and the statement says n ≤ 10⁶. What does the decision tree tell you to do?
8. 'Return the INDICES of two numbers (UNSORTED array) that sum to the target.' Why is two pointers NOT the best choice?
9. 'Largest PRODUCT of a contiguous subarray' (with negatives). What's the extra care over basic Kadane?
10. What is the mother idea that ALL the section's patterns share?
Ready for the exam?
The final exam has three brand-new problems — one easy, one medium and one hard — with hidden test cases, like the real LeetCode. Everything you need is in the 7 lessons of this section (and an honest tip: the decision tree up top solves the pattern choice for all three).
Good luck! Go back to the section page and click "Final exam".