Faangprep Logo
Log inStart free
Browse curriculum

Subarray Sum Equals K

Count the contiguous subarrays whose sum equals k in one pass, using a running prefix sum and a hash map of the sums seen so far.

MediumSolve on LeetCode

Problem Understanding

Count the contiguous, non-empty subarrays of the integer array nums whose elements add up to exactly k.

Strategy (HashMap + Prefix Sum)

We want Sum(i, j) == k.
Since Sum(i, j) = Prefix[j] - Prefix[i-1], we want:
Prefix[j] - Prefix[i-1] == k
=> Prefix[i-1] == Prefix[j] - k.

Algorithm:

  • Iterate through array, maintaining current_sum.

  • Check HashMap: how many times have we seen current_sum - k before?

  • Add that count to our answer.

  • Add current_sum to the HashMap.

Interactive Visualization

Each step adds one number to the running sum and looks up how many earlier prefix sums equal sum - k. Every one of them starts a subarray that ends here; the figure outlines each match.

Edge Cases

Watch out for:

  • Negative Numbers: Prefix sums are not monotonic! Cannot use Sliding Window (Two Pointers). Must use HashMap.

  • k = 0: Subarrays with sum 0 are valid.

  • Zeroes: Multiple zeroes increase count significantly.

Dry Run

Nums: [1, 1, 1], k=2. Map: {0:1}. Count=0. sum=0.

Num New Sum Check (Sum-k) Map Has Check? Action Map Update
1 1 1 - 2 = -1 No - {0:1, 1:1}
1 2 2 - 2 = 0 Yes (val=1) Count += 1 {0:1, 1:1, 2:1}
1 3 3 - 2 = 1 Yes (val=1) Count += 1 {0:1, 1:1, 2:1, 3:1}

Result: 2.

Solution

O(N) Time, O(N) Space.

Subarray Sum Equals K Code
1var subarraySum = function(nums, k) {
2    let count = 0;
3    let currSum = 0;
4    const map = new Map();
5    map.set(0, 1);
6    
7    for (const num of nums) {
8        currSum += num;
9        
10        if (map.has(currSum - k)) {
11            count += map.get(currSum - k);
12        }
13        
14        map.set(currSum, (map.get(currSum) || 0) + 1);
15    }
16    return count;
17};
Previous

Product of Array Except Self

The approach, step by step

  1. Seed the map

    Start with count = 0, sum = 0 and a map {0: 1}.

  2. Extend the running sum

    Add each number to sum, then add map[sum - k] to the count if it exists.

  3. Record the sum

    Increment map[sum], and return the count after the last number.

Frequently asked questions

How does the hash map solve Subarray Sum Equals K?

A subarray from j to i sums to k exactly when the prefix sum before j equals the running sum at i minus k. The map counts how many times each prefix sum has appeared, so each step adds all such subarrays at once.

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

It stands for the empty prefix before index 0. Without it, a subarray that starts at the first element and sums to k would never be counted.

Why can’t a sliding window solve Subarray Sum Equals K?

Negative numbers mean the running sum can go down as well as up, so moving a window’s edges does not reliably increase or decrease the sum. The prefix-sum map works for any integers in O(N) time and O(N) space.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description