INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED
01
00/15
01 / COVER MODULE 4 · HASHING & PREFIX SUMS
INVARIANT · MODULE 4 · HASHING & PREFIX SUMS
REMEMBER IT, DON'T RESCAN IT

Most O(n²) loops keep asking the same three things. Have I seen this? How often? What was the sum up to here? A hash map answers the first two in O(1), and a prefix array the third. Ten moves, fifteen problems.

15Problems
7Families
10Units
12Live walks
← → ↑ ↓  or  W A S D  navigate SPACE next   DOUBLE-CLICK to advance I index   G goto problem   P predict H hide solutions   F fullscreen
INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
02 / INDEX PRESS I FROM ANYWHERE

INDEX — ALL 15 PROBLEMS

Click any problem to jump straight to it. Solved ones turn green. Press I from anywhere to come back here. The number is the problem's fixed number in this deck, not a slide position.

SEEN BEFORE · 02
A KEY FOR THE GROUP · 01
COUNT, THEN READ · 02
PREFIX SUMS · 03
PREFIXES IN A MAP · 04
RANGES · 02
IN PLACE · 01
SOLVED HAS A JUDGE LINK
INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
03 / MECHANISM UNIT 01 · SEEN BEFORE

A LOOKUP SEARCHES ONE BUCKET

A hash set files x under bucket h(x). Asking for x reads that bucket only, so a lookup costs O(1) on average.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
04 / DRILL UNIT 01 · Seen Before · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

A hash set with buckets x % 4 holds 8, 3 and 12. A lookup of 20 compares it with which values?

20 % 4 = 0, the bucket of 8 and 12. 3 is in bucket 3, which is never read.

DRILL 02 · RECALL

Why is a hash-set lookup O(1) on average but O(n) in the worst case?

With a bad hash, all n values share a bucket and a lookup scans every one.

INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
05 / PROBLEM #01 · SEEN · EASY

Contains Duplicate

EASY seen ▶ SOLVE ON LEETCODE

GIVEN · ASKEDAn integer array. Return true if any value appears at least twice.

SIGNAL — WHAT GIVES IT AWAY

“Does any value appear twice?” One question per value: have I seen it before?

INTUITION

Keep a set of what has been read. A value already in the set is the duplicate.

STEPS
  1. Read each value in turn
  2. If it is in the set, return true
  3. Otherwise insert it
  4. Nothing repeated: return false
BRUTEO(n²) comparing every pair
→
OPTIMALO(n)
↕ SCROLL
bool containsDuplicate(vector<int>& nums) {
    unordered_set<int> seen;
    for (int x : nums) {
        if (seen.count(x)) return true;   // read before
        seen.insert(x);
    }
    return false;
}
TIMEO(n)one O(1) average lookup and insert per value
SPACEO(n)the set, up to n values
TRAP

Sorting when you could hash. Sorting and comparing neighbours is correct, but O(n log n), and it reorders the input.

INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
06 / PROBLEM #02 · SEEN · MED

Valid Sudoku

MED seen ▶ SOLVE ON LEETCODE

GIVEN · ASKEDA 9 × 9 Sudoku board, partly filled. Return true if no row, column or 3 × 3 box repeats a digit among its filled cells.

SIGNAL — WHAT GIVES IT AWAY

Each digit may appear once per row, once per column and once per 3 × 3 box. Three kinds of “seen before”.

INTUITION

One set per row, column and box, or one set of tagged keys. A digit already in any of its three units breaks the rule.

STEPS
  1. Skip the empty cells, '.'
  2. The box of (r, c) is (r / 3) · 3 + c / 3
  3. If d is already in the row, column or box, return false
  4. Otherwise record d in all three
BRUTEO(81²) comparing every pair of filled cells
→
OPTIMALO(81)
↕ SCROLL
bool isValidSudoku(vector<vector<char>>& board) {
    bool row[9][9] = {}, col[9][9] = {}, box[9][9] = {};   // [unit][digit]
    for (int r = 0; r < 9; r++)
        for (int c = 0; c < 9; c++) {
            if (board[r][c] == '.') continue;
            int d = board[r][c] - '1', b = (r / 3) * 3 + c / 3;
            if (row[r][d] || col[c][d] || box[b][d]) return false;
            row[r][d] = col[c][d] = box[b][d] = true;
        }
    return true;
}
TIMEO(81)each cell once, three O(1) checks
SPACEO(81)three 9 × 9 tables of flags
TRAP

Solving the puzzle. The question is only whether the filled cells break a rule. A board can be valid and still have no solution.

INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
07 / DRILL UNIT 01 · Seen Before · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

A 5 sits at row 4, column 7 of a Sudoku board. Which box is it in, with b = (r / 3) · 3 + c / 3?

(4 / 3) · 3 + 7 / 3 = 3 + 2 = 5: the middle band of boxes, the right column.

INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
08 / MECHANISM UNIT 02 · A KEY FOR THE GROUP

ONE KEY FOR THE WHOLE GROUP

Sort a word's letters and every anagram gives the same key. A map from key to list collects each group in one pass.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
09 / DRILL UNIT 02 · A Key for the Group · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · BUG

Which key wrongly puts two strings that are not anagrams in one group?

a + d and b + c have the same total, so ad and bc share it.

DRILL 02 · TRACE

groupAnagrams(["abc", "bca", "cab", "abd"]). How many groups?

abc, bca and cab all sort to abc. abd has its own key.

INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
10 / DRILL UNIT 02 · A Key for the Group · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

The words are long. Which key avoids sorting each one?

Counting is O(m) per word, and the counts fix the anagram group exactly.

INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
11 / PROBLEM #03 · KEYS · MED

Group Anagrams

MED keys ▶ SOLVE ON LEETCODE

GIVEN · ASKEDAn array of strings. Group the anagrams together, in any order.

SIGNAL — WHAT GIVES IT AWAY

“Group the strings that are anagrams.” Equal as multisets of letters, in any order.

INTUITION

Give every string a key that ignores order: its letters sorted. Anagrams get the same key, and a map from key to list collects them.

STEPS
  1. For each string, key = its letters, sorted
  2. Append the string to the list under that key
  3. Return the lists
BRUTEO(n² · m) comparing every pair of strings
→
OPTIMALO(n · m log m)
↕ SCROLL
vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> g;
    for (string& s : strs) {
        string key = s;
        sort(key.begin(), key.end());          // anagrams share this key
        g[key].push_back(s);
    }
    vector<vector<string>> out;
    for (auto& p : g) out.push_back(p.second);
    return out;
}
TIMEO(n · m log m)n strings of length m, each sorted once
SPACEO(n · m)every string is stored once in the map
TRAP

A key that collides. The sum of the letters, or the set of letters, gives "ab" and "aab" or "ad" and "bc" the same key. The key must determine every count.

INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
12 / MECHANISM UNIT 03 · COUNT FIRST, THEN READ

COUNT EVERYTHING, THEN READ

Pass 1 counts each letter. Pass 2 reads the string again and stops at the first count of 1. A count is final only at the end.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
13 / MECHANISM UNIT 03 · TOP K BY BUCKETS

THE COUNT IS THE INDEX

No value appears more than n times, so bucket[f] holds the values seen f times. Read from the top down: no sort.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
14 / DRILL UNIT 03 · Count First, Then Read · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

firstUniqChar("aabb")?

Both letters appear twice, so pass 2 never finds a count of 1.

INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
15 / PROBLEM #04 · COUNTS · EASY

First Unique Character in a String

EASY counts ▶ SOLVE ON LEETCODE

GIVEN · ASKEDA string of lowercase letters. Return the index of the first character that appears exactly once, or −1.

SIGNAL — WHAT GIVES IT AWAY

“The first character that does not repeat.” Whether it repeats depends on the whole string.

INTUITION

Count every letter in one pass. Then read the string again and return the first index whose letter has count 1.

STEPS
  1. Pass 1: count each letter
  2. Pass 2: from the left, return the first i with count 1
  3. None: return −1
BRUTEO(n²) counting each character's copies
→
OPTIMALO(n)
↕ SCROLL
int firstUniqChar(string s) {
    int cnt[26] = {};
    for (char c : s) cnt[c - 'a']++;                  // pass 1: count
    for (int i = 0; i < (int)s.size(); i++)
        if (cnt[s[i] - 'a'] == 1) return i;           // pass 2: read the counts
    return -1;
}
TIMEO(n)two passes
SPACEO(1)26 counters, whatever n is
TRAP

Deciding during the first pass. A letter with count 1 so far can still get a second copy later. Only finished counts are safe to read.

INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
16 / PROBLEM #05 · COUNTS · MED

Top K Frequent Elements

MED counts ▶ SOLVE ON LEETCODE

GIVEN · ASKEDAn integer array and k. Return the k most frequent values, in any order; the answer is unique.

SIGNAL — WHAT GIVES IT AWAY

“The k most frequent values.” Counts are at most n, so they can index an array.

INTUITION

Count each value. Put each value in bucket[count]. Read the buckets from count n down until k values are out.

STEPS
  1. Count each value with a map
  2. bucket[f] lists the values seen exactly f times
  3. Walk f from n down to 1, collecting values
  4. Stop at k
BRUTEO(n log n) sorting the distinct values by count
→
OPTIMALO(n)
↕ SCROLL
vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> cnt;
    for (int x : nums) cnt[x]++;
    vector<vector<int>> bucket(nums.size() + 1);      // bucket[f]: seen f times
    for (auto& p : cnt) bucket[p.second].push_back(p.first);
    vector<int> out;
    for (int f = nums.size(); f >= 1; f--)
        for (int x : bucket[f]) {
            out.push_back(x);
            if ((int)out.size() == k) return out;
        }
    return out;
}
TIMEO(n)counting, bucketing and the scan are each O(n)
SPACEO(n)the map and the n + 1 buckets
TRAP

Sorting the map by count. It works in O(n log n). The follow-up asks for better than that, and the counts are small integers, so they can index buckets.

INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
17 / DRILL UNIT 03 · Count First, Then Read · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

nums = [5, 5, 5, 7, 7, 9], k = 1. Which bucket is read first that is not empty, and what is returned?

5 is seen 3 times, the most. Buckets 6 to 4 are empty, so bucket 3 comes first.

DRILL 02 · RECALL

Why does bucket have n + 1 cells?

If one value fills the array, its count is n, so index n must exist.

INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
18 / MECHANISM UNIT 04 · PREFIX SUMS

ONE SUBTRACTION PER RANGE

P[i] is the sum of the first i values, with P[0] = 0. Then the sum of l..r is P[r + 1] − P[l].

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
19 / DRILL UNIT 04 · Prefix Sums · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

nums = [1, 2, 3, 4]. What is P, and what is sumRange(1, 3)?

P[4] − P[1] = 10 − 1 = 9, which is 2 + 3 + 4.

INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
20 / PROBLEM #06 · PREFIX · EASY

Range Sum Query - Immutable

EASY prefix ▶ SOLVE ON LEETCODE

GIVEN · ASKEDAn integer array, then many queries sumRange(left, right). Return each sum, both ends included.

SIGNAL — WHAT GIVES IT AWAY

Many range-sum queries on an array that never changes.

INTUITION

Build P with P[0] = 0 and P[i + 1] = P[i] + nums[i]. The sum of nums[l..r] is P[r + 1] − P[l].

STEPS
  1. P has n + 1 cells; P[0] = 0
  2. P[i + 1] = P[i] + nums[i]
  3. sumRange(l, r) = P[r + 1] − P[l]
BRUTEO(n) per query, adding the range each time
→
OPTIMALO(n) build, O(1) query
↕ SCROLL
class NumArray {
    vector<int> P;                                  // P[i]: sum of the first i
public:
    NumArray(vector<int>& nums) : P(nums.size() + 1, 0) {
        for (int i = 0; i < (int)nums.size(); i++) P[i + 1] = P[i] + nums[i];
    }
    int sumRange(int left, int right) {
        return P[right + 1] - P[left];
    }
};
TIMEO(n) build, O(1) queryone pass to build, one subtraction per query
SPACEO(n)the prefix array
TRAP

P of length n. Without the leading 0, a range that starts at index 0 needs its own case, and P[r] − P[l − 1] reads P[−1].

INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
21 / PROBLEM #07 · PREFIX · EASY

Find Pivot Index

EASY prefix ▶ SOLVE ON LEETCODE

GIVEN · ASKEDAn integer array. Return the leftmost index whose left sum equals its right sum, or −1.

SIGNAL — WHAT GIVES IT AWAY

“The sum to the left equals the sum to the right.” Two prefix sums, but one is the total minus the other.

INTUITION

Keep the sum to the left of i. The sum to the right is total − left − nums[i]. Return the first i where they match.

STEPS
  1. total = the sum of everything
  2. Walk i with left = the sum before i
  3. If left == total − left − nums[i], return i
  4. Then left += nums[i]
BRUTEO(n²) summing both sides at every index
→
OPTIMALO(n)
↕ SCROLL
int pivotIndex(vector<int>& nums) {
    int total = 0, left = 0;
    for (int x : nums) total += x;
    for (int i = 0; i < (int)nums.size(); i++) {
        if (left == total - left - nums[i]) return i;   // right side, without nums[i]
        left += nums[i];
    }
    return -1;
}
TIMEO(n)two passes
SPACEO(1)two running sums
TRAP

Updating left before the test. Then left includes nums[i] itself, and the pivot is found one place late, or not at all.

INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
22 / DRILL UNIT 04 · Prefix Sums · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

pivotIndex([2, 1, −1])?

At index 0 the left sum is 0, and the right sum is 1 + (−1) = 0. An empty side is 0.

DRILL 02 · BUG

A solution does left += nums[i] before the test. What does it return on [1, 7, 3, 6, 5, 6], whose pivot is 3?

left now includes nums[i], so the sides never match: at index 3 it compares 17 with 5.

INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
23 / MECHANISM UNIT 05 · FROM BOTH SIDES

LEFT TIMES RIGHT

Pass 1 writes the product to the left of each index. Pass 2 walks back and multiplies in the product to the right.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
24 / DRILL UNIT 05 · From Both Sides

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

productExceptSelf([1, 2, 0, 4])?

Every product but index 2's includes the 0. Index 2 gets 1 · 2 · 4 = 8.

DRILL 02 · TRACE

On [3, 1, 2, 5], what does ans hold after the first pass?

The product to the left of each index: nothing, 3, 3 · 1, then 3 · 1 · 2.

INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
25 / PROBLEM #08 · PREFIX · MED

Product of Array Except Self

MED prefix ▶ SOLVE ON LEETCODE

GIVEN · ASKEDAn integer array. Return ans where ans[i] is the product of every other element, in O(n) and without division.

SIGNAL — WHAT GIVES IT AWAY

“The product of all the others, without division, in O(n).”

INTUITION

ans[i] is (product to the left) × (product to the right). Write the left products in one pass, then multiply in the right products walking back.

STEPS
  1. ans[i] = product of nums[0..i − 1], with a running pre
  2. Walk back with a running suf: ans[i] *= suf
  3. suf *= nums[i] after using it
BRUTEO(n²) multiplying the others for each index
→
OPTIMALO(n)
↕ SCROLL
vector<int> productExceptSelf(vector<int>& nums) {
    int n = nums.size();
    vector<int> ans(n, 1);
    int pre = 1, suf = 1;
    for (int i = 0; i < n; i++) { ans[i] = pre; pre *= nums[i]; }        // left
    for (int i = n - 1; i >= 0; i--) { ans[i] *= suf; suf *= nums[i]; }  // right
    return ans;
}
TIMEO(n)two passes
SPACEO(1)besides the output, two running products
TRAP

Total product divided by nums[i]. One zero makes the total 0 and the division undefined, and the problem forbids division anyway.

INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
26 / MECHANISM UNIT 06 · THE EARLIEST PREFIX

KEEP THE EARLIEST INDEX OF EACH PREFIX

A subarray sums to k when two prefixes differ by k. Look up p − k; record p only the first time, so starts stay far left.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
27 / DRILL UNIT 06 · The Earliest Prefix · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

arr = [1, −1, 5, −2, 3], k = 3. What is the longest length?

The prefixes are 1, 0, 5, 3, 6. At index 3, p − k = 0, first seen at −1: length 4.

DRILL 02 · RECALL

Why can a sliding window not solve this when values may be negative?

A window shrinks when the sum is too big, which only works if growing never lowers it.

INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
28 / PROBLEM #09 · PREFIXMAP · MED

Longest Subarray with Sum K

MED prefixmap ▶ SOLVE ON GEEKSFORGEEKSGeeksforGeeks rates it Medium. The LeetCode version, 325, is paid.

GIVEN · ASKEDAn integer array, values may be negative, and k. Return the length of the longest subarray with sum k, or 0.

SIGNAL — WHAT GIVES IT AWAY

The longest subarray with sum exactly k, and values may be negative. A sliding window cannot work.

INTUITION

A subarray (j, i] sums to k when p(i) − p(j) = k. Map each prefix sum to the earliest index it appears at; at each i, look up p − k.

STEPS
  1. first[0] = −1, the empty prefix
  2. p += arr[i]; if p − k is in the map, best = max(best, i − first[p − k])
  3. Record p only if it is new: the earliest index wins
BRUTEO(n²) summing every subarray
→
OPTIMALO(n)
↕ SCROLL
int longestSubarray(vector<int>& arr, int k) {
    unordered_map<long long, int> first;       // prefix sum -> earliest index
    first[0] = -1;
    long long p = 0;
    int best = 0;
    for (int i = 0; i < (int)arr.size(); i++) {
        p += arr[i];
        auto it = first.find(p - k);
        if (it != first.end()) best = max(best, i - it->second);
        if (!first.count(p)) first[p] = i;     // keep the earliest
    }
    return best;
}
TIMEO(n)one pass, O(1) average per lookup
SPACEO(n)up to n + 1 distinct prefix sums
TRAP

Overwriting the index. first[p] = i every time keeps the latest start, which gives the shortest subarray, not the longest.

INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
29 / PROBLEM #10 · PREFIXMAP · MED

Contiguous Array

MED prefixmap ▶ SOLVE ON LEETCODE

GIVEN · ASKEDA binary array. Return the length of the longest subarray with as many 0s as 1s.

SIGNAL — WHAT GIVES IT AWAY

“Equal numbers of 0s and 1s.” Count a 0 as −1 and it becomes a subarray with sum 0.

INTUITION

Keep a balance: +1 for a 1, −1 for a 0. Two equal balances enclose a balanced subarray. Keep the earliest index of each balance.

STEPS
  1. first[0] = −1
  2. bal += 1 for a 1, −1 for a 0
  3. Seen before: best = max(best, i − first[bal])
  4. Otherwise record first[bal] = i
BRUTEO(n²) counting both digits in every subarray
→
OPTIMALO(n)
↕ SCROLL
int findMaxLength(vector<int>& nums) {
    unordered_map<int, int> first;             // balance -> earliest index
    first[0] = -1;
    int bal = 0, best = 0;
    for (int i = 0; i < (int)nums.size(); i++) {
        bal += nums[i] == 1 ? 1 : -1;           // a 0 counts as -1
        auto it = first.find(bal);
        if (it != first.end()) best = max(best, i - it->second);
        else first[bal] = i;
    }
    return best;
}
TIMEO(n)one pass
SPACEO(n)balances run from −n to n
TRAP

Forgetting first[0] = −1. A balanced prefix such as [0, 1] then has no earlier balance to match, and the answer comes out short.

INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
30 / DRILL UNIT 06 · The Earliest Prefix · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

findMaxLength([0, 1, 1, 0, 1, 1, 1, 0])?

The balance is 0 again at index 3, so indices 0 to 3 hold two of each. No balance repeats further apart.

INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
31 / MECHANISM UNIT 07 · COUNT MATCHING PREFIXES

COUNT THE PREFIXES THAT COMPLETE IT

A subarray XORs to k when the prefix before it XORs to x ^ k. Add how often that prefix was seen, then record x.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
32 / MECHANISM UNIT 07 · REMAINDERS MOD K

THE SAME REMAINDER ENCLOSES A MULTIPLE

Two prefixes with equal remainders mod k enclose a sum divisible by k. Count remainders, kept in 0..k − 1.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
33 / DRILL UNIT 07 · Count Matching Prefixes · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

arr = [5, 6, 7, 8, 9], k = 5. How many subarrays XOR to 5?

[5] and the whole array: 5 ^ 6 ^ 7 ^ 8 ^ 9 = 5.

DRILL 02 · TRANSFER

Subarray Sum Equals K, in Arrays I, counts subarrays with sum k. What does it look up at each step?

The same shape as XOR K with − for ^: an earlier prefix of p − k leaves exactly k.

INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
34 / PROBLEM #11 · PREFIXMAP · MED

Count Subarrays with XOR K

MED prefixmap ▶ SOLVE ON GEEKSFORGEEKSGeeksforGeeks rates it Medium. LeetCode has no free problem for it.

GIVEN · ASKEDAn integer array and k. Return how many subarrays have XOR equal to k.

SIGNAL — WHAT GIVES IT AWAY

“How many subarrays XOR to k?” The same shape as counting subarrays with a given sum, with ^ in place of −.

INTUITION

Let x be the prefix XOR. A subarray XORs to k when the prefix before it XORs to x ^ k. Count how often each prefix XOR has appeared.

STEPS
  1. cnt[0] = 1, the empty prefix
  2. x ^= arr[i]
  3. total += cnt[x ^ k]
  4. cnt[x]++
BRUTEO(n²) XORing every subarray
→
OPTIMALO(n)
↕ SCROLL
long subarrayXor(vector<int>& arr, int k) {
    unordered_map<int, long> cnt;              // prefix XOR -> how many times
    cnt[0] = 1;
    int x = 0;
    long total = 0;
    for (int a : arr) {
        x ^= a;
        auto it = cnt.find(x ^ k);             // the XOR before the start
        if (it != cnt.end()) total += it->second;
        cnt[x]++;
    }
    return total;
}
TIMEO(n)one pass
SPACEO(n)the count map
TRAP

Recording x before the lookup. When k = 0, x ^ k is x itself, and the prefix just added would count an empty subarray.

INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
35 / PROBLEM #12 · PREFIXMAP · MED

Subarray Sums Divisible by K

MED prefixmap ▶ SOLVE ON LEETCODE

GIVEN · ASKEDAn integer array, values may be negative, and k. Return how many subarrays have a sum divisible by k.

SIGNAL — WHAT GIVES IT AWAY

“Sum divisible by k.” Two prefixes with the same remainder enclose a multiple of k.

INTUITION

Count prefixes by remainder mod k. Each earlier prefix with the same remainder starts one valid subarray ending here. Keep remainders in 0..k − 1.

STEPS
  1. cnt[0] = 1
  2. p = ((p + x) % k + k) % k
  3. total += cnt[p]; then cnt[p]++
BRUTEO(n²) summing every subarray
→
OPTIMALO(n + k)
↕ SCROLL
int subarraysDivByK(vector<int>& nums, int k) {
    vector<int> cnt(k, 0);                     // remainder -> how many prefixes
    cnt[0] = 1;
    int p = 0, total = 0;
    for (int x : nums) {
        p = ((p + x) % k + k) % k;             // C++ % can be negative
        total += cnt[p];
        cnt[p]++;
    }
    return total;
}
TIMEO(n + k)one pass and the k counters
SPACEO(k)k counters
TRAP

A negative remainder. In C++ and Java, -1 % 5 is −1, so −1 and 4 land in different counters, or off the array. Add k and take % again.

INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
36 / DRILL UNIT 07 · Count Matching Prefixes · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

subarraysDivByK([−1, 2, 9], 2)?

The remainders are 1, 1, 0, after the empty prefix's 0. Two pairs match: [2] and the whole array, sum 10.

INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
37 / MECHANISM UNIT 08 · THE DIFFERENCE ARRAY

WRITE THE EDGES, SUM THE REST

A range update writes +s where it starts and −s just after it ends. One running sum rebuilds every value.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
38 / DRILL UNIT 08 · The Difference Array

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

n = 4 and bookings [[1, 3, 5], [2, 4, 2]]. What is d before the sweep?

+5 at d[0] and −5 at d[3], just after flight 3; +2 at d[1] and −2 at d[4].

DRILL 02 · TRACE

The running sums of that d are the answer. What is it?

5, then 5 + 2, then 7 + 0, then 7 − 5. The last cell, d[4], is never read.

INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
39 / PROBLEM #13 · RANGES · MED

Corporate Flight Bookings

MED ranges ▶ SOLVE ON LEETCODE

GIVEN · ASKEDn flights and bookings (first, last, seats). Return the total seats booked on each flight.

SIGNAL — WHAT GIVES IT AWAY

Each booking adds seats to a whole range of flights. Many range updates, then read every value once.

INTUITION

Mark +seats where a range starts and −seats just after it ends. A running sum turns the marks back into the values.

STEPS
  1. d has n + 1 cells
  2. For a booking (first, last, s): d[first − 1] += s, d[last] −= s
  3. ans[i] = d[0] + … + d[i]
BRUTEO(n · b) adding each booking to every flight in its range
→
OPTIMALO(n + b)
↕ SCROLL
vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
    vector<int> d(n + 1, 0);
    for (auto& b : bookings) {
        d[b[0] - 1] += b[2];                   // seats start at flight first
        d[b[1]] -= b[2];                       // and stop after flight last
    }
    vector<int> ans(n);
    int run = 0;
    for (int i = 0; i < n; i++) { run += d[i]; ans[i] = run; }
    return ans;
}
TIMEO(n + b)two writes per booking, one pass to sum
SPACEO(n)the difference array
TRAP

Ending the range one place early. Flights are numbered from 1, so d[last] is the cell just after flight last. d[last − 1] stops a flight too soon.

INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
40 / MECHANISM UNIT 09 · PREFIX SUMS IN 2D

A BLOCK, MINUS TWO STRIPS, PLUS THEIR OVERLAP

P[r][c] is the block above and left. Build it with one cell, two neighbours and the corner taken off; query with four reads.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
41 / DRILL UNIT 09 · Prefix Sums in 2D

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

m = [[1, 2], [3, 4]]. What is P[2][2]?

P[2][2] is the whole 2 × 2 block: 1 + 2 + 3 + 4.

DRILL 02 · RECALL

sumRegion(0, 0, r2, c2) starts at the top-left corner. Which term of the formula is not zero?

Row 0 and column 0 of P are zero, so the query is that one cell.

INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
42 / PROBLEM #14 · RANGES · MED

Range Sum Query 2D - Immutable

MED ranges ▶ SOLVE ON LEETCODE

GIVEN · ASKEDA matrix, then many queries sumRegion(row1, col1, row2, col2). Return each rectangle's sum.

SIGNAL — WHAT GIVES IT AWAY

Many rectangle-sum queries on a matrix that never changes.

INTUITION

P[r][c] is the sum of the block above row r and left of column c. A rectangle is a big block, minus two strips, plus their overlap.

STEPS
  1. P is (R + 1) × (C + 1), with row 0 and column 0 zero
  2. P[r+1][c+1] = m[r][c] + P[r][c+1] + P[r+1][c] − P[r][c]
  3. sumRegion = P[r2+1][c2+1] − P[r1][c2+1] − P[r2+1][c1] + P[r1][c1]
BRUTEO(R · C) per query, adding the rectangle each time
→
OPTIMALO(R · C) build, O(1) query
↕ SCROLL
class NumMatrix {
    vector<vector<int>> P;                     // P[r][c]: block above r, left of c
public:
    NumMatrix(vector<vector<int>>& m) {
        int R = m.size(), C = m[0].size();
        P.assign(R + 1, vector<int>(C + 1, 0));
        for (int r = 0; r < R; r++)
            for (int c = 0; c < C; c++)
                P[r + 1][c + 1] = m[r][c] + P[r][c + 1] + P[r + 1][c] - P[r][c];
    }
    int sumRegion(int r1, int c1, int r2, int c2) {
        return P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1];
    }
};
TIMEO(R · C) build, O(1) queryeach cell of P once, four reads per query
SPACEO(R · C)the prefix table
TRAP

Forgetting to add the overlap back. Both strips contain the block above and left of the query, so subtracting both removes it twice.

INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
43 / MECHANISM UNIT 10 · THE ARRAY AS ITS OWN HASH TABLE

VALUE v LIVES AT INDEX v − 1

Only 1..n can be the answer. Swap each such value home, then the first index without its value is the smallest missing positive.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
44 / DRILL UNIT 10 · The Array as Its Own Hash Table

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

firstMissingPositive([1, 2, 0])?

1 and 2 are home, and 0 has no home. Every index holds its value, so return n + 1 = 3.

DRILL 02 · BUG

The while tests nums[i] != i + 1 instead of nums[v − 1] != v. What happens on [1, 1]?

At index 1, v = 1 and nums[1] ≠ 2, so it swaps two 1s, and nothing changes.

INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
45 / PROBLEM #15 · INPLACE · HARD

First Missing Positive

HARD inplace ▶ SOLVE ON LEETCODE

GIVEN · ASKEDAn unsorted integer array. Return the smallest positive integer that is not in it, in O(n) time and O(1) extra space.

SIGNAL — WHAT GIVES IT AWAY

“The smallest missing positive, in O(n) time and O(1) extra space.” No room for a set, so the array becomes one.

INTUITION

The answer is in 1..n + 1, so only values 1 to n matter. Swap each one to index v − 1. Then the first index i that does not hold i + 1 gives the answer.

STEPS
  1. For each i: while 1 ≤ v ≤ n and nums[v − 1] ≠ v, swap v to index v − 1
  2. Then scan: the first i with nums[i] ≠ i + 1 returns i + 1
  3. All home: return n + 1
BRUTEO(n log n) sorting, or O(n) space with a set
→
OPTIMALO(n)
↕ SCROLL
int firstMissingPositive(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        int v = nums[i];
        while (v >= 1 && v <= n && nums[v - 1] != v) {
            swap(nums[i], nums[v - 1]);        // v goes home, to index v - 1
            v = nums[i];
        }
    }
    for (int i = 0; i < n; i++)
        if (nums[i] != i + 1) return i + 1;    // the first home still wrong
    return n + 1;
}
TIMEO(n)every swap puts one value home for good, so at most n swaps
SPACEO(1)the array itself is the table
TRAP

Testing nums[i] ≠ i + 1 in the while. With a duplicate, such as two 1s, the loop swaps the same value back and forth forever. Test whether v's home already holds v.

INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
46 / SIGNALS WHEN YOU SEE X, REACH FOR Y

WHICH MOVE, AND WHAT GIVES IT AWAY

Ten moves, and each has a phrase in the statement that gives it away.

“ANY DUPLICATE?” / “SEEN BEFORE?”

a set of what has been read; a lookup searches one bucket

SEEN BEFOREO(n)
“GROUP THE … THAT ARE THE SAME UP TO …”

a key equal across the group; a map from key to list

A KEY FOR THE GROUPO(n · key)
“FIRST UNIQUE” / “MOST FREQUENT”

count everything, then read; bucket[count] when the counts must be ordered

COUNT, THEN READO(n)
MANY RANGE SUMS, NO UPDATES

P[0] = 0 and P[i + 1] = P[i] + nums[i]; a range is P[r + 1] − P[l]

PREFIX SUMSO(1) per query
“EVERYTHING EXCEPT i”

the left part times the right part, one pass each way

FROM BOTH SIDESO(n)
“LONGEST” SUBARRAY WITH SUM k, NEGATIVES ALLOWED

map each prefix to its earliest index; look up p − k

THE EARLIEST PREFIXO(n)
“HOW MANY” SUBARRAYS: SUM, XOR, REMAINDER

count prefixes in a map; add the count of the partner, then record

COUNT MATCHING PREFIXESO(n)
ADD s TO EVERY CELL IN [l, r], MANY TIMES

+s at l, −s just after r; one running sum at the end

DIFFERENCE ARRAYO(n + updates)
RECTANGLE SUMS ON A FIXED MATRIX

P[r][c] is the block above and left; four reads per query

2D PREFIXO(1) per query
O(1) EXTRA SPACE, ANSWER IN 1..n + 1

send v to index v − 1; the first index without its value

THE ARRAY AS ITS OWN TABLEO(n)
INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
47 / RECALL RETRIEVAL, NOT RECOGNITION · 1 OF 2

NAME THE MOVE FROM THE STATEMENT

DRILL 01 · TRANSFER

Return the length of the longest subarray whose sum is 0. Which move?

Two equal prefix sums enclose a zero sum. Keep the earliest index of each one.

DRILL 02 · TRANSFER

Count the pairs i < j whose song lengths add up to a multiple of 60. Which move?

For each length, add how many earlier lengths have remainder (60 − r) % 60, then record r. A map of remainders, counted as you go.

INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
48 / RECALL RETRIEVAL, NOT RECOGNITION · 2 OF 2

NAME THE MOVE FROM THE STATEMENT

DRILL 01 · RECALL

Which of these starts its map with first[0] = −1 rather than cnt[0] = 1?

It asks for a length, so its map holds the earliest index. The counting rows hold how many.

DRILL 02 · RECALL

A difference array takes b range updates on n cells, then one sweep. What is the total cost?

Each update writes two cells, and the sweep reads n.

INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
49 / TRAPS PLAUSIBLE, WRONG, AND SILENT

SIX WAYS TO BE PLAUSIBLY WRONG

None of these fail the samples. Each one fails a hidden test.

OVERWRITING THE EARLIEST INDEX

For a longest subarray, record a prefix only the first time. Writing it every time keeps the latest start, which is the shortest.

FORGETTING THE EMPTY PREFIX

first[0] = −1, cnt[0] = 1. Without it, every subarray that starts at index 0 is missed.

A NEGATIVE REMAINDER

In C++ and Java, −1 % 5 is −1. Add k and take % again, or −1 and 4 never meet.

A SLIDING WINDOW WITH NEGATIVES

Growing a window can lower its sum, so shrinking on “too big” is wrong. Use prefix sums and a map.

RECORDING BEFORE LOOKING UP

Look up the partner, then record the current prefix. The other order counts an empty subarray when k = 0.

A KEY THAT COLLIDES

Summing the letter codes puts ad and bc together. The key must fix every letter's count.

INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
50 / CHEATSHEET REVISION SURFACE

ONE SCREEN, THE WHOLE DECK

Ten moves on one page. The right column is the cue for each.

ALGORITHM
TIME
SPACE
REACH FOR IT WHEN
Seen before
O(n)
O(n)
a duplicate, a value seen earlier; one bucket per lookup
A key for the group
O(n · key)
O(n)
anagrams, same pattern, same shape: map key → list
Count, then read
O(n)
O(n)
first unique, most frequent; bucket[count] for top k
Prefix sums
O(n) + O(1)
O(n)
range sums with no updates; P has n + 1 cells
From both sides
O(n)
O(1)
everything except i: the left part times the right part
The earliest prefix
O(n)
O(n)
a longest subarray with sum k; negatives allowed
Count matching prefixes
O(n)
O(n)
how many subarrays: sum, XOR or remainder
Difference array
O(n + b)
O(n)
many range additions, read once at the end
2D prefix
O(RC) + O(1)
O(RC)
rectangle sums: block − two strips + overlap
Array as its own table
O(n)
O(1)
values in 1..n and no room for a set
INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
51 / CLOSE MODULE 4 · HASHING & PREFIX SUMS

REMEMBER IT YOURSELF

Buckets answered “seen?”; sorted letters made a key; counts were read after they were final; prefixes turned ranges into subtractions, from one side, both sides, and in two dimensions; a map of prefixes found the earliest start or counted partners; edges stood in for whole ranges; and the array held its own values.

00%
OF THIS DECK SOLVED
← ALL TOPICS← ARRAYS ISLIDING WINDOW →

Module 4. Fifteen problems: thirteen on LeetCode, two on GeeksforGeeks. Next: two pointers.

INVARIANT · HASHING & PREFIX SUMS · SEEN, COUNTED, SUMMED · HASHING & PREFIX SUMS
■ TOO SMALL TO READ
1280×720
INVARIANT · MODULE 4 · HASHING & PREFIX SUMS

This one needs a laptop

Not a preference — an arithmetic one. Every slide is a fixed 1280 × 720 stage: a graph animating beside the code that drives it, with the problems laid out two columns wide. It scales as a single piece, so on a screen this size the body text comes out around 4px tall.

Shrinking it further would not help, and rebuilding it to reflow would mean losing the thing that makes it worth reading.

YOUR SCREEN0 × 0
NEEDED1060 × 610
WHAT IS WAITING ON THE LAPTOP
WATCH IT RUN, THEN RUN IT FROM MEMORY
Your progress is saved per device, so anything you tick on the laptop will be waiting there.