Prefix Sum — Subarray Sum Equals K

What does it solve?

Count how many contiguous subarrays sum to a target K. A prefix sum P[i] is the total of everything up to index i, so the sum of any range (j, i] is just P[i] − P[j].

Key insight: a subarray ending at i sums to K exactly when some earlier prefix equals P[i] − K. Store the count of every prefix seen so far in a hash map and look it up in O(1) — turning O(N²) into O(N).

The core idea

// running prefix + count map
count = {0: 1} // empty prefix
prefix = 0, ans = 0
for x in nums:
  prefix += x
  ans += count[prefix - k] // need
  count[prefix] += 1

Complexity

Time complexity

O(N)

One pass over the array. Each prefix lookup and insert into the hash map is O(1) on average.

Space complexity

O(N)

The count map can hold up to N distinct prefix sums in the worst case.

Examples & edge cases

Live animation — running prefix + count map

current element matched subarray map hit → count +=

Array — prefix under each cell

count map — prefix → times seen

i = — prefix = — need = — count = —

Step — of —

index i

—

current element

prefix sum

—

total so far

need (prefix − k)

—

look up in map

Subarrays found

—

running total

Select an example and press Play to start.

✓ Answer: —

Speed Medium

Step-by-step table

Step	i	num	prefix	need	hits	Action	count

C++ implementation

subarray_sum_k.cpp

#include <bits/stdc++.h>
using namespace std;

// Count subarrays summing to k via prefix sums
int subarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> count;
    count[0] = 1;              // empty prefix seen once
    int prefix = 0, ans = 0;

    for (int x : nums) {
        prefix += x;
        // a prefix equal to (prefix - k) closes a subarray summing to k
        if (count.count(prefix - k)) ans += count[prefix - k];
        count[prefix]++;
    }
    return ans;
}

int main() {
    vector<int> nums = {1, 1, 1};
    cout << subarraySum(nums, 2) << "\n"; // 2
    return 0;
}

My Notes

📝Notes✅

▼

●Start typing to save... 0 chars