Subarray Sum Equals K

mediumAmazon-tagged: Arrays & Strings31 stepsJava · Python · C++

Count contiguous subarrays summing to k. A subarray (j, i] sums to k exactly when prefix[i] − prefix[j] = k. Walk once keeping a map of how often each prefix sum has appeared; at each position add the count of prefix − k.

▶ Watch the animated trace

Traced input: nums = [1, 2, 3, -2, 2], k = 3 → 4. Original problem: neetcode.io/problems/subarray-sum-equals-k

Complexity

BestO(n)

AverageO(n)

WorstO(n)

SpaceO(n)

One pass with a hash map.

Key idea

Subarray sum = difference of two prefix sums.
seen.get(prefix - k) = number of earlier start points that work.
Seed the map with {0: 1} so subarrays starting at index 0 count.
Works with negative numbers, unlike a sliding window.

Common mistakes

Sliding window fails with negative numbers.
Forgetting the {0: 1} seed misses subarrays from the start.
Updating the map before checking counts the empty subarray when k = 0.

Solution

Java

int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> seen = new HashMap<>();
    seen.put(0, 1);
    int prefix = 0, count = 0;
    for (int i = 0; i < nums.length; i++) {
        prefix += nums[i];
        int add = seen.getOrDefault(prefix - k, 0);
        count += add;
        seen.merge(prefix, 1, Integer::sum);
    }
    return count;
}

Python

def subarraySum(nums: List[int], k: int) -> int:
    seen = Counter({0: 1})
    prefix = count = 0
    for x in nums:
        prefix += x
        count += seen[prefix - k]
        seen[prefix] += 1
    return count

C++

int subarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> seen{{0, 1}};
    int prefix = 0, count = 0;
    for (int x : nums) {
        prefix += x;
        auto it = seen.find(prefix - k);
        if (it != seen.end()) count += it->second;
        seen[prefix]++;
    }
    return count;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Repeated values [1,1] twice.	`nums = [1, 1, 1], k = 2`	`2`
k = 0 with zeros Every non-empty subarray: 3 + 2 + 1.	`nums = [0, 0, 0], k = 0`	`6`
Negative numbers [1,-1], [0], [1,-1,0].	`nums = [1, -1, 0], k = 0`	`3`
No subarray Total is only 3.	`nums = [1, 2], k = 5`	`0`