SimuVedaAlgorithms Lab Open in the lab

Patterns / Advanced

Prefix Sum + Hash Map Visualizer

If prefix[j] = prefix[i] − k, the values between j and i sum to k. A hash map remembers how often each prefix sum appeared.

Start the Prefix Sum + Hash Map simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n)
Average timeO(n)
Worst timeO(n)
Extra spaceO(n)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Store prefix sum 0 once, for subarrays that start at index 0. Looking for k = 7. [3, 4, 7, 2, -3, 1, 4, 2]
  2. Add 3. Prefix sum = 3.
  3. 3 − 7 = -4 has not been seen. No subarray ending here sums to 7.
  4. Record prefix sum 3 in the map.
  5. Add 4. Prefix sum = 7.
  6. 7 − 7 = 0 was seen 1 time. A subarray ends here with sum 7, like [0..1].
  7. Record prefix sum 7 in the map.
  8. Add 7. Prefix sum = 14.
  9. 14 − 7 = 7 was seen 1 time. A subarray ends here with sum 7, like [2..2].
  10. Record prefix sum 14 in the map.
  11. Add 2. Prefix sum = 16.
  12. 16 − 7 = 9 has not been seen. No subarray ending here sums to 7.
  13. Record prefix sum 16 in the map.
  14. Add -3. Prefix sum = 13.
  15. 13 − 7 = 6 has not been seen. No subarray ending here sums to 7.
  16. Record prefix sum 13 in the map.
  17. Add 1. Prefix sum = 14.
  18. 14 − 7 = 7 was seen 1 time. A subarray ends here with sum 7, like [2..5].
  19. Record prefix sum 14 in the map.
  20. Add 4. Prefix sum = 18.
  21. … 2 more steps …
  22. Add 2. Prefix sum = 20.
  23. 20 − 7 = 13 was seen 1 time. A subarray ends here with sum 7, like [5..7].
  24. Record prefix sum 20 in the map.
  25. Done. 4 subarrays sum to 7.

Try it with your own input →

Prefix sum + hash map in Java, Python, C++, C and JavaScript

int subarraySum(int[] a, int k) {
  Map<Integer, Integer> seen = new HashMap<>();
  seen.put(0, 1);
  int sum = 0, count = 0;
  for (int x : a) {
    sum += x;
    count += seen.getOrDefault(sum - k, 0);
    seen.merge(sum, 1, Integer::sum);
  }
  return count;
}
def subarray_sum(a, k):
    seen = {0: 1}
    s = count = 0
    for x in a:
        s += x
        count += seen.get(s - k, 0)
        seen[s] = seen.get(s, 0) + 1
    return count
int subarraySum(const vector<int>& a, int k) {
  unordered_map<int, int> seen;
  seen[0] = 1;
  int sum = 0, count = 0;
  for (int x : a) {
    sum += x;
    auto it = seen.find(sum - k);
    if (it != seen.end()) count += it->second;
    seen[sum]++;
  }
  return count;
}
#include <stdlib.h>

/* Tiny open-addressing map from prefix sum to how often it was seen. */
#define SIZE 4096
int keys[SIZE], vals[SIZE], used[SIZE];
int *slot(int key) {
  unsigned h = (unsigned)key * 2654435761u % SIZE;
  while (used[h] && keys[h] != key) h = (h + 1) % SIZE;
  if (!used[h]) { used[h] = 1; keys[h] = key; vals[h] = 0; }
  return &vals[h];
}

int subarraySum(int a[], int n, int k) {
  for (int i = 0; i < SIZE; i++) used[i] = 0;
  *slot(0) = 1;
  int sum = 0, count = 0;
  for (int x = 0; x < n; x++) {
    sum += a[x];
    count += *slot(sum - k);
    (*slot(sum))++;
  }
  return count;
}
function subarraySum(a, k) {
  const seen = new Map();
  seen.set(0, 1);
  let sum = 0, count = 0;
  for (const x of a) {
    sum += x;
    count += seen.get(sum - k) || 0;
    seen.set(sum, (seen.get(sum) || 0) + 1);
  }
  return count;
}

In an interview

LeetCode 560, Subarray Sum Equals K: count the subarrays that add up to k.

Do not forget map.put(0, 1). It counts subarrays that start at index 0, and missing it is the most common bug.

More patterns