beta

2.2 Hashing · cheat sheet

Prefix sum with a hash map.

Count subarrays with a given sum, including negative values.

Spot it: the words in the question

how many streaks add up to a total
consecutive entries
negative values are allowed
a run that nets to a target
running total
subarray sum equals

The invariant

Before each entry is read, the table counts every earlier running total, the empty start included, so one lookup counts all the runs that end at that entry.

The pattern

Pattern cardPrefix sum with a hash map

Use it when you must count, or measure, runs of consecutive entries whose total meets an exact condition, and entries may be negative. Signal words: consecutive entries, add up to, how many streaks, the longest streak, negative values.

Start: a map from running total to a count, or to a position, that holds the total 0 for the empty start.

Step: add the entry to the running total. Look up total - target. Use what is found. Then store the current total.

Stop: when the entries run out.

It does not answer "at least" or "at most" questions. A lookup finds one exact total.

Cost: O(n) time on average and O(n) space. Trying every streak costs O(n^2) time.

Complexity

Time. The pass reads each entry once and makes one lookup and at most one insert. With a hash table that stays roomy, each costs one step on average. So n entries cost O(n).
Worst case. If many totals share one bucket, each lookup walks a long chain, and the pass degrades towards O(n^2). A good hash and a resizing table make this unlikely.
Space. The table holds up to n + 1 different totals: O(n).
Size. Running totals can reach 10^5 entries × 10^6 each, which is 10^11. That needs a 64-bit integer. The count of runs can reach about 5 × 10^9, which needs one too.
Trade. The streak scan uses O(1) extra space and O(n^2) time. The table uses O(n) space and O(n) time. At 100,000 entries, the table turns 5 × 10^9 additions into about 200,000 operations.

Templates · Python

The lesson’s templates, checked in all four languages against the same test cases.

Code in four languagesCount the runs: how many streaks add up to the target

pythoncount_runs · 14 lines

def count_runs(amounts, target):
    # [1] A table of how often each running total has occurred. The empty start has total 0, once.
    seen = {0: 1}
    total = 0
    count = 0
    for amount in amounts:
        # [2] The running total after this entry.
        total += amount
        # [3] Each earlier running total equal to total - target ends a run that adds up to the target.
        count += seen.get(total - target, 0)
        # [4] Record this running total, after the lookup.
        seen[total] = seen.get(total, 0) + 1
    # [5] The number of runs.
    return count

java17 lines

public long countRuns(int[] amounts, int target) {
    // [1] A table of how often each running total has occurred. The empty start has total 0, once.
    java.util.HashMap<Long, Integer> seen = new java.util.HashMap<>();
    seen.put(0L, 1);
    long total = 0;
    long count = 0;
    for (int amount : amounts) {
        // [2] The running total after this entry.
        total += amount;
        // [3] Each earlier running total equal to total - target ends a run that adds up to the target.
        count += seen.getOrDefault(total - target, 0);
        // [4] Record this running total, after the lookup.
        seen.put(total, seen.getOrDefault(total, 0) + 1);
    }
    // [5] The number of runs.
    return count;
}

c++20 lines

long long countRuns(vector<int>& amounts, int target) {
    // [1] A table of how often each running total has occurred. The empty start has total 0, once.
    unordered_map<long long, int> seen;
    seen[0] = 1;
    long long total = 0;
    long long count = 0;
    for (int amount : amounts) {
        // [2] The running total after this entry.
        total += amount;
        // [3] Each earlier running total equal to total - target ends a run that adds up to the target.
        auto it = seen.find(total - target);
        if (it != seen.end()) {
            count += it->second;
        }
        // [4] Record this running total, after the lookup.
        seen[total] += 1;
    }
    // [5] The number of runs.
    return count;
}

javascriptcountRuns · 16 lines

function countRuns(amounts, target) {
  // [1] A table of how often each running total has occurred. The empty start has total 0, once.
  const seen = new Map([[0, 1]]);
  let total = 0;
  let count = 0;
  for (const amount of amounts) {
    // [2] The running total after this entry.
    total += amount;
    // [3] Each earlier running total equal to total - target ends a run that adds up to the target.
    count += seen.get(total - target) ?? 0;
    // [4] Record this running total, after the lookup.
    seen.set(total, (seen.get(total) ?? 0) + 1);
  }
  // [5] The number of runs.
  return count;
}

Code in four languagesThe longest run: the length of the longest streak that adds up to the target

pythonlongest_run · 16 lines

def longest_run(amounts, target):
    # [1] A table from each running total to the first position where it occurred. Position 0 is the empty start.
    first_at = {0: 0}
    total = 0
    best = 0
    for position in range(1, len(amounts) + 1):
        # [2] The running total after reading this many entries.
        total += amounts[position - 1]
        # [3] If total - target occurred earlier, the entries after that position add up to the target.
        if total - target in first_at:
            best = max(best, position - first_at[total - target])
        # [4] Record only the first position of a total: the earliest start gives the longest run.
        if total not in first_at:
            first_at[total] = position
    # [5] The length of the longest run, or 0 when there is none.
    return best

java21 lines

public int longestRun(int[] amounts, int target) {
    // [1] A table from each running total to the first position where it occurred. Position 0 is the empty start.
    java.util.HashMap<Long, Integer> firstAt = new java.util.HashMap<>();
    firstAt.put(0L, 0);
    long total = 0;
    int best = 0;
    for (int position = 1; position <= amounts.length; position++) {
        // [2] The running total after reading this many entries.
        total += amounts[position - 1];
        // [3] If total - target occurred earlier, the entries after that position add up to the target.
        if (firstAt.containsKey(total - target)) {
            best = Math.max(best, position - firstAt.get(total - target));
        }
        // [4] Record only the first position of a total: the earliest start gives the longest run.
        if (!firstAt.containsKey(total)) {
            firstAt.put(total, position);
        }
    }
    // [5] The length of the longest run, or 0 when there is none.
    return best;
}

c++22 lines

int longestRun(vector<int>& amounts, int target) {
    // [1] A table from each running total to the first position where it occurred. Position 0 is the empty start.
    unordered_map<long long, int> firstAt;
    firstAt[0] = 0;
    long long total = 0;
    int best = 0;
    for (int position = 1; position <= (int)amounts.size(); position++) {
        // [2] The running total after reading this many entries.
        total += amounts[position - 1];
        // [3] If total - target occurred earlier, the entries after that position add up to the target.
        auto it = firstAt.find(total - target);
        if (it != firstAt.end()) {
            best = max(best, position - it->second);
        }
        // [4] Record only the first position of a total: the earliest start gives the longest run.
        if (!firstAt.count(total)) {
            firstAt[total] = position;
        }
    }
    // [5] The length of the longest run, or 0 when there is none.
    return best;
}

javascriptlongestRun · 20 lines

function longestRun(amounts, target) {
  // [1] A table from each running total to the first position where it occurred. Position 0 is the empty start.
  const firstAt = new Map([[0, 0]]);
  let total = 0;
  let best = 0;
  for (let position = 1; position <= amounts.length; position++) {
    // [2] The running total after reading this many entries.
    total += amounts[position - 1];
    // [3] If total - target occurred earlier, the entries after that position add up to the target.
    if (firstAt.has(total - target)) {
      best = Math.max(best, position - firstAt.get(total - target));
    }
    // [4] Record only the first position of a total: the earliest start gives the longest run.
    if (!firstAt.has(total)) {
      firstAt.set(total, position);
    }
  }
  // [5] The length of the longest run, or 0 when there is none.
  return best;
}

Pitfalls

✕ 1Forgetting the empty start
This version starts with an empty table.
✕ 2Storing before looking up
This version adds the new total to the table first, and then looks up total - target.
✕ 3The sliding window
A tempting method grows a window to the right and shrinks it from the left while the total is above the target. It works when entries are never negative. With negative entries, a longer window can have a smaller total.
✕ 4Counting each total once
This version keeps a set of the totals seen, instead of how often each occurred. A total that occurred twice still counts once.

Test these

An empty ledger
A target of zero
Zeros make many runs
Negative targets and refunds

Not this pattern

At least the target

Your team lead asks for the streaks that add up to at least 100 units, or at most 100. Many different totals qualify, and one lookup finds one exact total. The table cannot answer a question about a range.

Practise it

systemdesignmastery.dev/dsa/cheatsheets/prefix-sum-hashmap