Basics
The idea behind the pattern, why it is correct, and the clues in a question that point to it.
1.1Core idea
What the pattern does, in plain words.
A hash map turns 'have I seen the value I need?' into O(1). Prefix sums turn any subarray sum into a difference of two prefixes, so 'subarray sums to K' becomes 'seen prefix − K?'.
The sum of nums[i..j] equals prefix[j] minus prefix[i − 1]. So 'some subarray ending here sums to k' becomes 'some earlier prefix equals prefix − k', which a hash map answers in O(1). Hashing in general turns 'have I seen this before?' from a scan into a lookup.
Typical cost: O(n) time, O(n) space
1.2Recognition signals
If a question has one of these clues, try this pattern first.
Question
A classic interview problem from this family. Read it carefully and plan the approach before writing any code.
2.1Longest Consecutive Sequence
The problem statement, then the plan you would say out loud.
Unsorted integers; return the length of the longest run of consecutive values, in O(n).
Plan before you code
- Put everything in a set.
- Only start counting from numbers whose predecessor is missing.
- Each number is visited a constant number of times.
Detailed answer
First the reusable template, then the worked solution built from it and a walk through it one step at a time.
3.1Template
Memorise this shape. Most problems in this family are this code plus one twist.
Count subarrays summing to k
1function subarraySum(nums: number[], k: number): number {2 const seen = new Map<number, number>([[0, 1]]); // prefix sum -> count3 let prefix = 0, count = 0;4 for (const x of nums) {5 prefix += x;6 count += seen.get(prefix - k) ?? 0;7 seen.set(prefix, (seen.get(prefix) ?? 0) + 1);8 }9 return count;10}1fun subarraySum(nums: IntArray, k: Int): Int {2 val seen = hashMapOf(0 to 1) // prefix sum -> count3 var prefix = 04 var count = 05 for (x in nums) {6 prefix += x7 count += seen[prefix - k] ?: 08 seen[prefix] = (seen[prefix] ?: 0) + 19 }10 return count11}1static int subarraySum(int[] nums, int k) {2 Map<Integer, Integer> seen = new HashMap<>();3 seen.put(0, 1); // prefix sum -> count4 int prefix = 0, count = 0;5 for (int x : nums) {6 prefix += x;7 count += seen.getOrDefault(prefix - k, 0);8 seen.merge(prefix, 1, Integer::sum);9 }10 return count;11}- An empty prefix (sum 0) has been seen once.
- A subarray ending here sums to k if prefix − k was seen.
- Record this prefix for later positions.
3.2Solution
Strict TypeScript, type-checked and tested.
Longest Consecutive Sequence
1function longestConsecutive(nums: number[]): number {2 const s = new Set(nums);3 let best = 0;4 for (const x of s) {5 if (s.has(x - 1)) continue; // x is not the start of a run6 let y = x;7 while (s.has(y + 1)) y++;8 best = Math.max(best, y - x + 1);9 }10 return best;11}1fun longestConsecutive(nums: IntArray): Int {2 val s = nums.toHashSet()3 var best = 04 for (x in s) {5 if (s.contains(x - 1)) continue // x is not the start of a run6 var y = x7 while (s.contains(y + 1)) y++8 best = maxOf(best, y - x + 1)9 }10 return best11}1static int longestConsecutive(int[] nums) {2 Set<Integer> s = new HashSet<>();3 for (int x : nums) s.add(x);4 int best = 0;5 for (int x : s) {6 if (s.contains(x - 1)) continue; // x is not the start of a run7 int y = x;8 while (s.contains(y + 1)) y++;9 best = Math.max(best, y - x + 1);10 }11 return best;12}Step by step
- A set gives O(1) membership checks.
- Only start counting where a run begins (x − 1 is missing).
- Walk the run and keep the longest.
Complexity: O(n) time, O(n) space
Q&A
What interviewers ask once your code works, and problems to try on your own.
4.1Interview questions
Answer out loud, then open.
Why start the map with {0: 1}?
Why does this handle negative numbers when a sliding window cannot?
What makes a good hash key?
4.2Solo practice
Try these without looking; open the hint only when stuck.
Hint
Store value → index; look up target − x.
Extra depth
More fully worked problems in the same family, and the mistakes that cost offers.
5.12 more worked problems
Each one: the problem, the plan, the code and its cost.
Show detailsHide details
Group Anagrams
Group words that are anagrams of each other.
- Anagrams share the same letter counts.
- Join the 26 letter counts into a string key: O(L) per word, no sorting.
1function groupAnagrams(words: string[]): string[][] {2 const groups = new Map<string, string[]>();3 for (const w of words) {4 const counts = new Array<number>(26).fill(0);5 for (const ch of w) counts[ch.charCodeAt(0) - 97]++;6 const key = counts.join("#");7 if (!groups.has(key)) groups.set(key, []);8 groups.get(key)!.push(w);9 }10 return [...groups.values()];11}Complexity: O(total characters) time and space
Product of Array Except Self
out[i] = product of every element except nums[i], without division, in O(n).
- out[i] = (product of everything left of i) × (product of everything right of i).
- One pass left to right, one pass right to left, in the output array.
1function productExceptSelf(nums: number[]): number[] {2 const n = nums.length;3 const out = new Array<number>(n).fill(1);4 let left = 1;5 for (let i = 0; i < n; i++) {6 out[i] = left;7 left *= nums[i];8 }9 let right = 1;10 for (let i = n - 1; i >= 0; i--) {11 out[i] *= right;12 right *= nums[i];13 }14 return out;15}Complexity: O(n) time, O(1) extra space besides the output
5.2Traps
Bugs and misreadings that come up again and again with this pattern.
Show detailsHide details
- Forgetting the {0: 1} seed
- Updating the map before the lookup (counts itself)