Subarray Sum Equals K – Solution & Complexity
Watch: Subarray Sum Equals K with prefix sums
Brute force tries every start and end: O(n²). A grow-and-shrink sliding window finds only 2 of the 3 answers on [1, 2, −1, 2, 1] with k = 3, because dropping a negative makes the sum go up. Instead, keep running sums (0, 1, 3, 2, 4, 5): a subarray is a later sum minus an earlier one, so at each step add how many times sum − k has been seen, using a hash map seeded with {0: 1}. Look up before you record. O(n) time, O(n) space.
Solution Walkthrough
Step 1: Reframe as prefix sums
- Let
prefix[i]be the sum of the firstielements. - The sum of the subarray
(i, j]isprefix[j] - prefix[i]. - We want pairs where that difference equals
k.
- Let
Step 2: Brute-force every subarray
- Try every start index and extend a running sum to every end index.
- Count whenever the running sum hits
k. This isO(n^2).
Step 3: Count complementary prefixes
- Walk once, keeping the running prefix sum.
- For each prefix, the number of valid subarrays ending here equals how many earlier prefixes equalled
prefix - k. - Seed the map with
{0: 1}so subarrays starting at index0are counted.
Step 4: One-pass hashmap solution
- Store how many times each prefix sum has occurred.
- Add
counts[prefix - k]to the answer before recording the current prefix.
Step 5: Dry run
Trace
nums = [1, 1, 1],k = 2, starting withcounts = {0: 1}.num prefix prefix - k added counts 1 1 -1 0 {0:1, 1:1}1 2 0 1 {0:1, 1:1, 2:1}1 3 1 1 {0:1, 1:1, 2:1, 3:1}Total
= 2.Step 6: Final solution and complexity
The prefix-sum hashmap counts every qualifying subarray in
O(n)time andO(n)extra space.