Approach Summary
Track prefix sums in a hash map. At each position, if (currentSum - k) exists in the map, that count is the valid subarrays ending here.
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Full Solution & Approach
The sum of any subarray [j, i] equals prefix[i] - prefix[j-1], so asking for subarrays summing to k is asking for pairs of prefix sums that differ by k. Maintain a running prefix sum and a hash map counting how many times each prefix value has occurred. At each index, the number of subarrays ending here that sum to k equals the count of (running - k) already seen in the map — because every previous prefix that equals running - k forms exactly one valid subarray ending here. Then record the current running prefix in the map and continue. Initialize the map with {0: 1} so a subarray starting at index 0 is counted. This converts a brute-force O(n²) pair scan into a single pass — the canonical prefix-sum-plus-hash-map pattern that also solves longest-equal-sum and contiguous-array problems.
One pass with O(1) map operations per element — O(n) time. The map holds up to n distinct prefix sums — O(n) space.
Solution Code
Solution
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> counts = new HashMap<>();
counts.put(0, 1);
int running = 0, total = 0;
for (int n : nums) {
running += n;
total += counts.getOrDefault(running - k, 0);
counts.merge(running, 1, Integer::sum);
}
return total;
}int subarraySum(const vector<int>& nums, int k) {
unordered_map<int,int> counts;
counts[0] = 1;
int running = 0, total = 0;
for (int n : nums) {
running += n;
total += counts[running - k];
counts[running]++;
}
return total;
}def subarray_sum(nums: list[int], k: int) -> int:
counts = {0: 1}
running = 0
total = 0
for n in nums:
running += n
total += counts.get(running - k, 0)
counts[running] = counts.get(running, 0) + 1
return totalfunction subarraySum(nums, k) {
const counts = new Map([[0, 1]]);
let running = 0;
let total = 0;
for (const n of nums) {
running += n;
total += counts.get(running - k) || 0;
counts.set(running, (counts.get(running) || 0) + 1);
}
return total;
}Edge Cases to Watch
- Negative numbers — prefix sums are not monotonic, but the hash map handles any values
- k = 0 — counts subarrays summing to zero, including empty-ish runs
- A single element equal to k
- The whole array summing to k — handled by the {0: 1} initialization
Master the Prefix Sum Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Prefix Sum pattern.
How to Recognize This Pattern
- Count subarrays with exact sum
- Prefix sum + hash map
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)