Coding Interview PatternsSubarray Sum Equals K
MediumHash Maps
Subarray Sum Equals K
Explanation & Solution
Description
Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.
A subarray is a contiguous non-empty sequence of elements within an array.
Input:nums = [1, 1, 1], k = 2
0
1
1
1
2
1
Output: 2
Explanation: The subarrays [1, 1] starting at index 0 and [1, 1] starting at index 1 both sum to 2.
Constraints
1 <= nums.length <= 2 * 10⁴-1000 <= nums[i] <= 1000-10⁷ <= k <= 10⁷
Approach
Hash Maps pattern
1. Initialize a Prefix Sum Map
- Create a hash map
prefixCountto store how many times each prefix sum has occurred - Initialize with
{0: 1}because a prefix sum of 0 occurs once before we start (the empty prefix) - Set
sum = 0for the running prefix sum andcount = 0for the result
2. Iterate Through the Array
- For each element
nums[i], add it to the runningsum - This
sumrepresents the prefix sum from index 0 to indexi
3. Check for Valid Subarrays
- If
prefixCountcontains the keysum - k, it means there exist previous prefix sums such that the subarray between those positions and the current position sums tok - Add
prefixCount.get(sum - k)tocountbecause each such prefix represents a valid subarray
4. Update the Map
- Record the current
sumin the map by incrementing its count - This ensures future iterations can find subarrays ending after this point
5. Return the Result
- After processing all elements,
countholds the total number of subarrays whose sum equalsk
Key Insight
- The key observation is that
sum(i, j) = prefixSum(j) - prefixSum(i - 1). So ifprefixSum(j) - khas been seen before, then there exists a subarray ending atjwith sumk.
Time
O(n)single pass through the arraySpace
O(n)hash map stores at most n + 1 prefix sumsVisualization
Input:
[1, 1, 1], k = 2
—
No animation available
Left (L)Right (R)ConvergedDone
0 steps