Prefix Sum

Prefix + HashMap

Store prefix sums in a hash map. To find a subarray with sum K: if prefix[j] − K exists in the map, there's a valid subarray ending at j. This solves 'subarray sum equals K' in O(n).

O(n)

How It Works

Prefix sums combined with a hash map answer 'how many subarrays sum to K' in one pass. As you scan, maintain the running sum and a map from each prefix-sum value to how many times it has occurred. A subarray ending at the current index sums to K exactly when some earlier prefix equals runningSum − K, so you add the map's count for that value to the answer, then record the current prefix.

Brute force examines all O(n²) subarrays. The map turns 'find an earlier prefix with the right value' into an O(1) lookup, giving O(n) time and O(n) space. Seeding the map with {0: 1} counts subarrays that start at index zero.

Step-by-Step Visualization

Find subarrays with sum = 2

Prefix0

Count0

Map

0 1

1/4

Code

Java

static int subarraySum(int[] nums, int k) {
  Map<Integer, Integer> map = new HashMap<>();
  map.put(0, 1);
  int prefix = 0, count = 0;

  for (int num : nums) {
    prefix += num;
    if (map.containsKey(prefix - k)) count += map.get(prefix - k);
    map.put(prefix, map.getOrDefault(prefix, 0) + 1);
  }

  return count;
}

// Example: subarraySum(new int[]{1,1,1}, 2) → 2

Tips & Gotchas

1Store prefix sums in a hash map with their counts

2If prefixSum - k exists in the map, there is a subarray with sum k

3Initialize map with {0: 1} to handle subarrays starting at index 0

Practice Problems

1Subarray Sum Equals K
2Contiguous Array
3Subarray Sums Divisible by K
4Continuous Subarray Sum

About the Prefix Sum Pattern

Build an auxiliary array where each element stores the cumulative sum from the start. Then any range sum [i, j] is just prefix[j] − prefix[i−1] in O(1). Transforms repeated sum queries from O(n) to O(1) each.

Key insight

When you see 'subarray', 'contiguous', or 'in-place', think arrays. The key is reducing brute-force O(n²) to O(n) using sliding window, two pointers, or prefix sums.

Common Array Interview Problems

Two Sum
Best Time to Buy & Sell Stock
Maximum Subarray
Merge Intervals
Product of Array Except Self
Container With Most Water

Frequently Asked Questions

Why can't I use a sliding window for Subarray Sum Equals K?

Sliding windows require monotonicity: growing the window must move the sum in one direction. With negative numbers present, expanding can either raise or lower the sum, so the shrink decision becomes ambiguous. The prefix-plus-hashmap approach has no such requirement.

Why must the map be seeded with a prefix sum of 0?

The empty prefix — before any element — has sum 0 and represents subarrays starting at index 0. Without the {0: 1} entry, a prefix that itself equals K would find no match and those subarrays would be silently missed.

How does the divisibility variant change the map?

For 'sum divisible by K', store prefix sums modulo K instead of raw values, since two prefixes with equal remainders bracket a divisible subarray. Take care to normalize negative remainders into the range [0, K) in languages where the % operator can return negatives.