LeetCode 560 - Subarray Sum Equals K

LeetCode Problem 560

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Prefix Sum

Solution

Problem Understanding

The problem asks us to count how many contiguous, non-empty subarrays in an integer array nums have a sum equal to a target value k.

A subarray is different from a subsequence. Since the elements must remain contiguous, we only consider segments of the array that occupy consecutive positions. For example, in [1,2,3], [1,2] and [2,3] are valid subarrays, while [1,3] is not.

The input consists of:

• nums, an integer array that may contain positive numbers, negative numbers, and zeros
• k, the target sum we want subarrays to equal

The output should be a single integer representing the total number of subarrays whose sum equals k.

For example, given nums = [1,1,1] and k = 2, there are two valid subarrays:

• [1,1] at indices [0,1]
• [1,1] at indices [1,2]

So the answer is 2.

The constraints provide important hints about the intended solution:

• nums.length can be as large as 20,000
• Values range from -1000 to 1000
• k can be negative or positive

A naive solution that checks every possible subarray in quadratic or cubic time may struggle at the upper bound. More importantly, because negative numbers are allowed, common optimizations such as the sliding window technique do not work reliably. Sliding windows depend on sums increasing predictably when expanding the window, but negative values break this property.

Several edge cases deserve attention:

• Arrays containing negative numbers, because they invalidate monotonic assumptions.
• Arrays with many zeros, since multiple overlapping subarrays may produce the same sum.
• Cases where k = 0, which often expose prefix sum mistakes.
• Single element arrays, where the element itself may or may not equal k.
• Repeated prefix sums, since they indicate multiple matching subarrays ending at the same position.

Approaches

Brute Force Approach

The most direct approach is to check every possible subarray.

We can iterate through every starting index i, then expand the subarray ending index j from i to the end of the array while maintaining a running sum. Whenever the running sum equals k, we increment the count.

This works because every possible contiguous subarray is explicitly examined, guaranteeing correctness.

However, there are O(n²) possible subarrays. Since n can reach 20,000, checking all subarrays becomes expensive. While maintaining a running sum avoids the extra O(n) work of recomputing sums, the algorithm still performs roughly 200 million operations in the worst case.

Key Insight for an Optimal Solution

The important observation is that we can reformulate the problem using prefix sums.

Suppose:

$$prefixSum[i]$$

represents the sum of all elements from index 0 through i.

If a subarray from index j+1 to i sums to k, then:

$$prefixSum[i] - prefixSum[j] = k$$

Rearranging:

$$prefixSum[j] = prefixSum[i] - k$$

This means that for every current prefix sum, we only need to know how many previous prefix sums equal currentSum - k.

A hash map is perfect for this. It allows us to quickly count how many times each prefix sum has appeared so far.

Instead of checking all subarrays explicitly, we process the array once while maintaining:

• the current prefix sum
• a hash map of prefix sum frequencies
• the total number of matching subarrays

This reduces the complexity from quadratic to linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks every subarray using a running sum
Optimal	O(n)	O(n)	Uses prefix sums with a hash map

Algorithm Walkthrough

Optimal Algorithm Using Prefix Sum + Hash Map

1. Initialize a variable prefix_sum = 0.

This stores the cumulative sum as we iterate through the array. 2. Create a hash map to track prefix sum frequencies.

The key is a prefix sum value, and the value is how many times that sum has appeared.

We start with:

prefix_count = {0: 1}

This is crucial because it handles cases where a subarray starting at index 0 directly sums to k. 3. Initialize result = 0.

This variable counts valid subarrays. 4. Iterate through each number in nums.

For every element:

• Add the current number to prefix_sum
• Compute:

$$needed = prefix_sum - k$$

If needed exists in the hash map, then each occurrence represents a valid previous prefix sum that forms a subarray summing to k. 5. Add the frequency of needed to the result.

Since multiple matching prefix sums may exist, we add the full count. 6. Update the hash map.

Record the current prefix_sum so future elements can use it. 7. Continue until the entire array is processed. 8. Return result.

Why it works

The algorithm relies on the prefix sum identity:

$$subarray_sum = prefixSum[i] - prefixSum[j]$$

Whenever:

$$prefixSum[j] = prefixSum[i] - k$$

the subarray between those indices sums to k.

The hash map ensures we always know how many valid earlier prefix sums exist. Since every position is processed exactly once, every valid subarray is counted exactly once.

Python Solution

from typing import List

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        prefix_sum = 0
        result = 0
        prefix_count = {0: 1}

        for num in nums:
            prefix_sum += num

            needed_sum = prefix_sum - k
            result += prefix_count.get(needed_sum, 0)

            prefix_count[prefix_sum] = (
                prefix_count.get(prefix_sum, 0) + 1
            )

        return result

The implementation begins by initializing three key variables.

prefix_sum stores the cumulative sum while traversing the array. result keeps track of how many valid subarrays have been found. prefix_count is a dictionary that records how many times each prefix sum has appeared.

The initialization {0: 1} is important. It represents an empty prefix before the array begins. Without it, subarrays starting from index 0 would not be counted correctly.

Inside the loop, each number is added to the running prefix sum. The algorithm then computes needed_sum = prefix_sum - k. If this value exists in the dictionary, it means there are previous positions that create a subarray summing to k.

After counting matches, the current prefix sum is added to the dictionary so later elements can reference it.

Finally, the method returns the total count.

Go Solution

func subarraySum(nums []int, k int) int {
	prefixSum := 0
	result := 0

	prefixCount := map[int]int{
		0: 1,
	}

	for _, num := range nums {
		prefixSum += num

		neededSum := prefixSum - k
		result += prefixCount[neededSum]

		prefixCount[prefixSum]++
	}

	return result
}

The Go implementation follows the same logic as the Python version. A map[int]int stores prefix sum frequencies.

One convenient feature in Go is that accessing a missing map key returns the zero value for the type, so:

prefixCount[neededSum]

automatically returns 0 if the key does not exist.

No special handling for nil or empty arrays is necessary because the problem guarantees at least one element.

Integer overflow is not a concern here because the constraints keep cumulative sums safely within Go's integer range.

Worked Examples

Example 1

Input:

nums = [1,1,1], k = 2

Step	Num	Prefix Sum	Needed Sum	Matches Found	Result	Hash Map
Start	-	0	-	-	0	{0:1}
1	1	1	-1	0	0	{0:1, 1:1}
2	1	2	0	1	1	{0:1, 1:1, 2:1}
3	1	3	1	1	2	{0:1, 1:1, 2:1, 3:1}

Final answer:

2

The matching subarrays are:

• [1,1] from indices [0,1]
• [1,1] from indices [1,2]

Example 2

Input:

nums = [1,2,3], k = 3

Step	Num	Prefix Sum	Needed Sum	Matches Found	Result	Hash Map
Start	-	0	-	-	0	{0:1}
1	1	1	-2	0	0	{0:1,1:1}
2	2	3	0	1	1	{0:1,1:1,3:1}
3	3	6	3	1	2	{0:1,1:1,3:1,6:1}

Final answer:

2

The matching subarrays are:

• [1,2]
• [3]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is processed exactly once
Space	O(n)	Hash map may store up to n distinct prefix sums

The algorithm performs a single pass through the array. Every hash map lookup and insertion runs in average O(1) time, making the total runtime linear.

The extra space comes from storing prefix sums in the hash map. In the worst case, every cumulative sum is unique, requiring O(n) additional memory.

Test Cases

sol = Solution()

assert sol.subarraySum([1, 1, 1], 2) == 2  # provided example 1
assert sol.subarraySum([1, 2, 3], 3) == 2  # provided example 2

assert sol.subarraySum([1], 1) == 1  # single element matches k
assert sol.subarraySum([1], 2) == 0  # single element does not match

assert sol.subarraySum([0, 0, 0], 0) == 6  # multiple overlapping zero subarrays
assert sol.subarraySum([1, -1, 0], 0) == 3  # negative numbers and zero target

assert sol.subarraySum([-1, -1, 1], 0) == 1  # negative values
assert sol.subarraySum([3, 4, 7, 2, -3, 1, 4, 2], 7) == 4  # classic prefix sum case

assert sol.subarraySum([1, 2, 1, 2, 1], 3) == 4  # repeated valid subarrays
assert sol.subarraySum([1000] * 100, 1000) == 100  # repeated identical elements

Test	Why
[1,1,1], k=2	Validates provided example
[1,2,3], k=3	Confirms single element and multi element subarrays
[1], k=1	Smallest valid matching input
[1], k=2	Smallest non-matching input
[0,0,0], k=0	Verifies overlapping zero-sum subarrays
[1,-1,0], k=0	Ensures negatives are handled correctly
[-1,-1,1], k=0	Confirms behavior with negative values
[3,4,7,2,-3,1,4,2], k=7	Classic prefix sum stress case
[1,2,1,2,1], k=3	Tests repeated matching ranges
[1000]*100, k=1000	Verifies repeated values and scaling

Edge Cases

Arrays Containing Negative Numbers

Negative numbers make this problem tricky because techniques like sliding windows fail. With negative values, expanding a window can decrease the sum unexpectedly.

For example:

nums = [1, -1, 1]

A naive sliding window would not work reliably. The prefix sum method handles this naturally because it depends only on cumulative differences, not monotonic growth.

Multiple Overlapping Zero Sum Subarrays

When many zeros exist, multiple overlapping subarrays can sum to the same value.

For example:

nums = [0,0,0], k = 0

The valid subarrays are:

[0]
[0]
[0]
[0,0]
[0,0]
[0,0,0]

The implementation correctly counts all six because repeated prefix sums accumulate frequencies in the hash map.

Subarrays Starting at Index Zero

A common bug occurs when the desired subarray begins at the start of the array.

For example:

nums = [2,1], k = 2

Without initializing:

{0: 1}

the algorithm would miss [2] because there would be no earlier prefix sum to subtract. The implementation explicitly includes this initial state, ensuring such subarrays are counted correctly.