/Projects
Coding patterns · 05 of 15

Prefix sums and hashing

Remember what you have seen to answer in O(1).

PracticeCoding patternTier 2 · MechanismsApply15 minCore engineering

You will be able to: spot prefix sums and hashing from a problem statement, and code it from memory.

Interview prepCoding patterns

Study with AI

O(n) time, O(n) space Watch as reels
Part 1 of 5

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?'.

Why it works

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.

Two Sum style complement lookupsCount subarrays with sum KRange sum queriesGroup by a signature (anagrams)
Part 2 of 5

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.

Problem

Unsorted integers; return the length of the longest run of consecutive values, in O(n).

Plan before you code

  1. Put everything in a set.
  2. Only start counting from numbers whose predecessor is missing.
  3. Each number is visited a constant number of times.
Part 3 of 5

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

count-subarrays-summing.tsTypeScript
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}
10 linesUTF-8TypeScript
  1. An empty prefix (sum 0) has been seen once.
  2. A subarray ending here sums to k if prefix − k was seen.
  3. Record this prefix for later positions.

3.2Solution

Strict TypeScript, type-checked and tested.

Longest Consecutive Sequence

longest-consecutive-sequence.tsTypeScript
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}
11 linesUTF-8TypeScript

Step by step

  1. A set gives O(1) membership checks.
  2. Only start counting where a run begins (x − 1 is missing).
  3. Walk the run and keep the longest.

Complexity: O(n) time, O(n) space

Part 4 of 5

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}?
It stands for the empty prefix, so subarrays that start at index 0 are counted too.
Why does this handle negative numbers when a sliding window cannot?
It never shrinks a window; it only looks up exact prefix values, so the signs of the numbers do not matter.
What makes a good hash key?
Something compared by value, such as a number or a string. In TypeScript, arrays are compared by reference, so join them into a string first.

4.2Solo practice

Try these without looking; open the hint only when stuck.

EasyTwo Sum
Hint

Store value → index; look up target − x.

Part 5 of 5

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
Medium

Group Anagrams

Group words that are anagrams of each other.

  1. Anagrams share the same letter counts.
  2. Join the 26 letter counts into a string key: O(L) per word, no sorting.
group-anagrams.tsTypeScript
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}
11 linesUTF-8TypeScript

Complexity: O(total characters) time and space

Medium

Product of Array Except Self

out[i] = product of every element except nums[i], without division, in O(n).

  1. out[i] = (product of everything left of i) × (product of everything right of i).
  2. One pass left to right, one pass right to left, in the output array.
product-array-except.tsTypeScript
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}
15 linesUTF-8TypeScript

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)
AI Engineer · Prefix sums and hashing