prefix-sums · Problem 1 of 1
Subarray Sum Equals K
Stripe
Meta
AmazonCount the contiguous subarrays of nums whose values sum to k.
subarraySum([1, 1, 1], 2) -> 2
Both [1,1] windows count — subarrays are counted by position, not by content.
The values can be negative, which is what rules out a sliding window: with negatives the running sum is not monotone, so shrinking from the left does not reliably reduce it. This is the problem where prefix sums and hashing meet.
Your solution
Runs your code and animates it without grading anything. Change the input to see what it does on a case the tests do not cover.
Tests
5 cases, 1 hidden| call | type | expected | result |
|---|---|---|---|
| subarraySum([1,1,1], 2) | two overlapping windows | 2 | — |
| subarraySum([1,2,3], 3) | whole array and a prefix | 2 | — |
| subarraySum([1,-1,0], 0) | zeros make several empty-sum windows | 3 | — |
| subarraySum([1,2,3], 100) | nothing sums to k | 0 | — |
| withheld | hidden | withheld | — |
Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.
Complexity
- target time
- O(n)
- target space
- O(n)
One pass with a map holding at most n distinct prefix sums. The brute force over every start and end is O(n²), and the sliding window that would fix that is unavailable here because negative values break its monotonicity.
Hints
Stuck? Hints open one at a time, each giving a little more away.
3 hints left