Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Prefix Sums with a Hash Map

Editorial

When a window can't help

Subarray Sum Equals K: how many contiguous subarrays of [1, 2, -1, 2, -2, 3, -1, 2] add up to 3? There are 6: [1, 2], [2, −1, 2], [2, −2, 3], [3], [2, −1, 2, −2, 3, −1] and [−1, 2, −2, 3, −1, 2].

A sliding window looks tempting: grow it on the right, shrink it from the left while the sum is too big. That rule only works if adding a value always makes the sum bigger, and here values can be negative:

def count_with_window(nums, k):              # the sliding window: right only when no value is negative
    count = left = total = 0
    for right, x in enumerate(nums):
        total += x
        while total > k and left <= right:
            total -= nums[left]
            left += 1
        if total == k:
            count += 1
    return count

It counts 3 of the 6. Once a −1 or −2 is in the window, "too big, so shrink" throws away starts that a later negative value would have rescued.

Checking every subarray is always right:

def subarray_sum_slow(nums, k):
    count = 0
    for start in range(len(nums)):
        total = 0
        for end in range(start, len(nums)):      # every subarray that starts here
            total += nums[end]
            if total == k:
                count += 1
    return count

It returns 6, but it tries every pair of start and end: for the problem's 20,000 values that's 200,010,000 subarrays. We need a way to count them without looking at each one.

Go back to the picture from Introduction to Prefix Sums. A subarray is two fences, and its sum is the end fence's total minus the start fence's. Read that backwards: for a sum of k, the start must stand exactly k below the end. So walk the end fence along once, and at each one ask: how many fences so far stood at my total minus k?

The running totals of [1, 2, -1, 2, -2, 3, -1, 2] drawn as a walk of dots over fences 0 to 8: 0, 1, 3, 2, 4, 2, 5, 4, 6. The end is fence 6 (total 5) and k is 3, so a dashed line marks where a start must stand: 5 − 3 = 2. Fences 3 and 5 sit on it, and brackets over the values show the two subarrays that end at fence 6. Beside the walk, the hash map of the totals before fence 6, total to times seen: 4 → 1, 3 → 1, 2 → 2, 1 → 1, 0 → 1. Looking up 2 finds 2: two subarrays end here.

Move the end, ask the map

Remembering every earlier total and scanning them would be O(n²) again. A hash map from total → how many fences had it answers "how many stood at this height?" in one lookup.

Try it below. Press Next fence to move the end. The dashed line is the height a start needs; the green dots on it are the starts that work, and the map underneath says how many there are without looking at them. Click any earlier dot to check a start by hand. Then untick the 0 → 1 box, the map's starting entry, and step through again: at fence 2 the start the subarray [1, 2] needs is fence 0 itself, and the map no longer knows about it.

Prefix Pairs: move the end fence and watch which starts make the sum k

Two things to notice. The same total can appear at several fences (2 at fences 3 and 5), so the map keeps a count, not just yes or no: one lookup can find two subarrays. And fence 0 is a real fence with total 0: every subarray that starts at index 0 needs it, which is why the map starts as {0: 1}.

The template

Add the value, ask the map for the total minus k, then record the total:

Subarray Sum Equals K on [1, 2, -1, 2, -2, 3, -1, 2], k = 3 — Top: the values, and the running totals as they're reached. Bottom: the map from each total to how many fences had it, with the lookup highlighted.

int subarraySum(const vector<int>& nums, int k) {
    unordered_map<long long, int> seen;             // running total -> how many fences had it
    seen[0] = 1;                                    // fence 0: the total before any value
    long long total = 0;
    int count = 0;
    for (int x : nums) {
        total += x;
        auto it = seen.find(total - k);             // starts that stand k below this fence
        if (it != seen.end()) count += it->second;
        seen[total]++;                              // record this fence after the lookup
    }
    return count;
}

def subarray_sum(nums, k):
    seen = {0: 1}                                # running total -> how many fences had it
    total = count = 0
    for x in nums:
        total += x
        count += seen.get(total - k, 0)          # starts that stand k below this fence
        seen[total] = seen.get(total, 0) + 1     # record this fence after the lookup
    return count

static int subarraySum(int[] nums, int k) {
    Map<Long, Integer> seen = new HashMap<>();      // running total -> how many fences had it
    seen.put(0L, 1);                                // fence 0: the total before any value
    long total = 0;
    int count = 0;
    for (int x : nums) {
        total += x;
        count += seen.getOrDefault(total - k, 0);   // starts that stand k below this fence
        seen.merge(total, 1, Integer::sum);         // record this fence after the lookup
    }
    return count;
}

function subarraySum(nums, k) {
    const seen = new Map([[0, 1]]);                 // running total -> how many fences had it
    let total = 0, count = 0;
    for (const x of nums) {
        total += x;
        count += seen.get(total - k) ?? 0;          // starts that stand k below this fence
        seen.set(total, (seen.get(total) ?? 0) + 1); // record this fence after the lookup
    }
    return count;
}

Each prints 6, 2, 2 and 3 for [1, 2, -1, 2, -2, 3, -1, 2] with k = 3, [1, 1, 1] with k = 2, [1, 2, 3] with k = 3, and [10, 2, -2, -20, 10] with k = −10. One pass with one lookup and one insert per value: O(n) time on average, O(n) space for the map.

Ask, then record. The lookup must only see fences before this one. Record first and k = 0 finds the current fence itself, an empty subarray (the second mistake below).

How many, or the longest

Change what the map remembers and the same walk answers a different question. For the longest subarray with sum k, a count is useless; what matters is the first fence that reached each total, because the earliest start gives the longest subarray. So store the first index and never overwrite it. Fence 0 becomes index −1 (the length is i − (−1) = i + 1):

def longest_with_sum(nums, k):
    first = {0: -1}                              # running total -> the first index that reached it
    total = best = 0
    for i, x in enumerate(nums):
        total += x
        if total - k in first:
            best = max(best, i - first[total - k])
        if total not in first:                   # keep the first: an earlier start is a longer subarray
            first[total] = i
    return best

It prints 6, 6 and 5 for [1, 2, -1, 2, -2, 3, -1, 2] with k = 3, [10, 5, 2, 7, 1, -10] with k = 15, and [-5, 8, -14, 2, 4, 12] with k = −5. In the widget, switch to Longest with sum k and the map shows first fences instead of counts. Longest Subarray with Zero Sum is this with k = 0.

Contiguous Array (the longest subarray with as many 0s as 1s) looks different, but count each 0 as −1 and "equal 0s and 1s" becomes "sum 0":

def find_max_length(nums):
    first = {0: -1}
    total = best = 0
    for i, x in enumerate(nums):
        total += 1 if x == 1 else -1             # a 0 counts as -1: equal 0s and 1s add up to 0
        if total in first:
            best = max(best, i - first[total])
        else:
            first[total] = i
    return best

It prints 2, 2 and 6 for [0, 1], [0, 1, 0] and [0, 0, 1, 0, 0, 0, 1, 1].

Divisible by k: compare remainders

Subarray Sums Divisible by K: a subarray's sum is a multiple of k exactly when its two fences' totals have the same remainder mod k (their difference then has remainder 0). So keep the remainder instead of the total, and count how many earlier fences share it. Remainders run from 0 to k − 1, so an array of k counts does the map's job, the way an array of 26 does for letters.

Here the languages differ. In Python -1 % 5 is 4. In C++, Java and JavaScript it's −1: % keeps the sign of the left side. A negative total would then get a different remainder from a positive total it should match, so those three shift it with ((r + x) % k + k) % k:

int subarraysDivByK(const vector<int>& nums, int k) {
    vector<int> seen(k, 0);                         // remainder -> how many fences had it
    seen[0] = 1;                                    // fence 0: total 0, remainder 0
    int r = 0, count = 0;
    for (int x : nums) {
        r = ((r + x) % k + k) % k;                  // C++'s % can be negative: shift it into 0..k-1
        count += seen[r];                           // same remainder: the difference divides by k
        seen[r]++;
    }
    return count;
}

def subarrays_div_by_k(nums, k):
    seen = [0] * k                               # remainder -> how many fences had it
    seen[0] = 1                                  # fence 0: total 0, remainder 0
    r = count = 0
    for x in nums:
        r = (r + x) % k                          # Python's % is already in 0..k-1
        count += seen[r]                         # same remainder: the difference divides by k
        seen[r] += 1
    return count

static int subarraysDivByK(int[] nums, int k) {
    int[] seen = new int[k];                        // remainder -> how many fences had it
    seen[0] = 1;                                    // fence 0: total 0, remainder 0
    int r = 0, count = 0;
    for (int x : nums) {
        r = ((r + x) % k + k) % k;                  // Java's % can be negative: shift it into 0..k-1
        count += seen[r];                           // same remainder: the difference divides by k
        seen[r]++;
    }
    return count;
}

function subarraysDivByK(nums, k) {
    const seen = new Array(k).fill(0);              // remainder -> how many fences had it
    seen[0] = 1;                                    // fence 0: total 0, remainder 0
    let r = 0, count = 0;
    for (const x of nums) {
        r = ((r + x) % k + k) % k;                  // JavaScript's % can be negative: shift it into 0..k-1
        count += seen[r];                           // same remainder: the difference divides by k
        seen[r]++;
    }
    return count;
}

Each prints 7, 0 and 2 for [4, 5, 0, -2, -3, 1] with k = 5, [5] with k = 9, and [-1, 2, 9] with k = 2. Keeping only the remainder also means the running value never grows, so it can't overflow.

Continuous Subarray Sum asks whether some subarray of at least two values is a multiple of k. Keep the first index of each remainder, and answer yes when a later index repeats it at least 2 away:

def check_subarray_sum(nums, k):
    first = {0: -1}                              # remainder -> the first index that reached it
    r = 0
    for i, x in enumerate(nums):
        r = (r + x) % k
        if r in first:
            if i - first[r] >= 2:                # at least two values between the fences
                return True
        else:
            first[r] = i                         # keep the first, never move it later
    return False

It prints True, False, True and False for [23, 2, 4, 6, 7] with k = 6, [23, 2, 6, 4, 7] with k = 13, [1, 0, 0] with k = 2, and [0] with k = 1. In [1, 0, 0] the two 0s add up to 0, which counts as a multiple of 2.

XOR works the same way

A subarray's XOR is the XOR of its two fences' running XORs, and XOR undoes itself. So for a target k, the start's running XOR must be the current one XOR k. Count subarrays with given XOR:

def count_xor(nums, k):
    seen = {0: 1}                                # running XOR -> how many fences had it
    x = count = 0
    for v in nums:
        x ^= v
        count += seen.get(x ^ k, 0)              # a start whose XOR, undone, leaves k
        seen[x] = seen.get(x, 0) + 1
    return count

It prints 4 and 2 for [4, 2, 2, 6, 4] with k = 6 and [5, 6, 7, 8, 9] with k = 5.

Spotting it

Reach for running totals and a hash map when you see:

  • a contiguous subarray (or substring) whose sum is exactly k, a multiple of k, or 0;
  • "as many of this as of that" (count one kind as +1 and the other as −1);
  • count them or the longest one;
  • values that can be negative, which rules out the window.

And the near-misses:

  • every value is positive and the question is the longest or shortest stretch with a sum limit: a sliding window does it in O(1) space (Variable-Size Sliding Window: Longest and Shortest). Binary Subarrays With Sum can go either way.
  • at least k, with negative values (Shortest Subarray with Sum at Least K): a hash map only finds exact totals, so this needs a monotonic deque over the running totals, in Queues & Deques.
  • a subsequence, not a subarray (Target Sum): the values needn't be next to each other, so there are no fences. That's dynamic programming.
  • the same question in a grid: fix a top and a bottom row, add up each column between them, and run this lesson's walk on those sums.

Common mistakes

Starting with an empty map. seen = {} instead of {0: 1}

On [1, 2, -1, 2, -2, 3, -1, 2] with k = 3 it returns 5 instead of 6. The missing one is [1, 2]: its start is fence 0, total 0, which never got recorded. Every subarray that starts at index 0 is lost this way.

Recording before asking. seen[total] += 1 above the lookup

With k = 0, each total finds itself. [1, 2, 3] has no subarray that adds up to 0, yet it returns 3: one empty subarray per value.

Overwriting the first index. first[total] = i on every step

For the longest subarray, the latest fence with a total is the worst start. On [1, -1, 1, -1, 2] with k = 2 it returns 1 instead of 5. Only store a total the first time you see it.

A negative remainder in Java, C++ or JavaScript. int r = total % k

On [-1, 2, 9] with k = 2, Java returns 1 instead of 2. The total −1 gets remainder −1 and the total 1 gets remainder 1, so two fences that differ by 2 never meet. Shift it: ((total % k) + k) % k.

Moving the first index in Continuous Subarray Sum. first[r] = i even when r is already there

On [1, 0, 0] with k = 2 it returns False. The remainder 1 appears at indexes 0, 1 and 2; moving it to index 1 leaves only 1 between the fences at index 2, and the pair [0, 0] is missed.

Check yourself

Quiz

1 / 6

Multiple choice

Why does the map start as {0: 1}?

Practice problems

From easier to harder:

  1. Subarray Sum Equals K: the template.
  2. Longest Subarray with Zero Sum: first index, k = 0.
  3. Longest Subarray with sum K (All Integers): first index, any k.
  4. Contiguous Array: count 0 as −1, then the longest sum 0.
  5. Subarray Sums Divisible by K: remainders, shifted to be non-negative.
  6. Continuous Subarray Sum: first index of each remainder, at least two apart.
  7. Count subarrays with given XOR: running XORs.

Next, Difference Arrays and 2D Prefix Sums runs the running total backwards to apply many range updates at once, and takes it into two dimensions.