20. Subarray Sum Equals K
mediumAsked at RedisSubarray Sum Equals K counts how many contiguous slices of an integer array sum to exactly k — and because values can be negative, sliding windows break and the prefix-sum hashmap becomes the only linear path. Redis candidates report it as a favorite medium because the core identity, sum(i..j) = prefix[j] - prefix[i-1], is the same cumulative-counter thinking an in-memory data store applies to range queries over append-only streams.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Redis loops.
- LeetCode (2026)— Problem #560 'Subarray Sum Equals K' — canonical statement, the negative-value range that rules out sliding windows, and medium rating.
- Google Search Console (InterviewChamp) (2026-Q2)— Live search-demand data shows candidates searching this problem paired with Redis interview prep.
Problem
Given an integer array nums and an integer k, return the total number of contiguous, non-empty subarrays whose elements sum to exactly k. Values may be negative, so windows can both grow and shrink a running sum — the structure that makes two-pointer approaches unsound here.
Constraints
1 <= nums.length <= 2 * 10^4-1000 <= nums[i] <= 1000-10^7 <= k <= 10^7Negative values mean prefix sums are NOT monotonic — the property that invalidates sliding-window solutions.
Examples
Example 1
nums=[1,1,1], k=22Explanation: Two windows hit the target: [1,1] starting at index 0 and [1,1] starting at index 1 — overlapping subarrays count separately.
Example 2
nums=[1,2,3], k=32Explanation: [1,2] and [3] both sum to 3. The prefix-sum view: prefix values are 1, 3, 6, and both 3-3=0 and 6-3=3 have been seen before.
Approaches
1. Nested sum
Enumerate every (i, j) subarray; add nums[j] to running sum and compare.
- Time
- O(n^2)
- Space
- O(1)
let count = 0;
for (let i = 0; i < nums.length; i++) {
let s = 0;
for (let j = i; j < nums.length; j++) {
s += nums[j];
if (s === k) count++;
}
}
return count;Tradeoff: Quadratic but constant-space, and at n = 20,000 it is ~200 million additions — borderline on the judge and an automatic 'can you do better?' in a live interview. Useful only as the correctness baseline you state in one breath.
2. Prefix sum + hash map
Walk once with running sum S; for each S add seen[S - k] to count, then bump seen[S]. The map stores how many prefixes ended at each cumulative value.
- Time
- O(n)
- Space
- O(n)
function subarraySum(nums, k) {
const seen = new Map();
seen.set(0, 1);
let sum = 0, count = 0;
for (const n of nums) {
sum += n;
count += seen.get(sum - k) || 0;
seen.set(sum, (seen.get(sum) || 0) + 1);
}
return count;
}Tradeoff: Linear time for O(n) map space — the accepted optimum. The subtlety that earns the hire signal: seeding seen with {0: 1} so subarrays starting at index 0 are counted, and explaining why counts (not booleans) must be stored when prefix values repeat.
Redis-specific tips
Redis candidates report the discussion steering toward how the prefix-sum identity generalizes: a store built on cumulative counters answers 'how many events in this range?' by subtracting two running totals rather than re-scanning, which is exactly sum(i..j) = prefix[j] - prefix[i-1]. In the coding portion, the two graded moments are seeding the map with {0: 1} unprompted and explaining why negative numbers kill the sliding-window alternative. If asked to extend, sketch persisting the running map so multiple consumers of one stream share the same range-count index.
Common mistakes
- Forgetting to seed the map with {0: 1} — every subarray that starts at index 0 is silently dropped.
- Storing booleans instead of counts — when the same prefix value occurs multiple times (guaranteed possible with negatives), each earlier occurrence is a distinct valid start.
- Updating seen[S] BEFORE looking up seen[S - k] — when k = 0 the window matches itself and overcounts.
- Trying a sliding window — with negative values the running sum is not monotonic, so shrinking the window can both raise and lower the sum and the pointer logic is unsound.
Follow-up questions
An interviewer at Redis may pivot to one of these next:
- Continuous Subarray Sum (LC 523): same map trick but on prefix-sum REMAINDERS modulo k — store earliest index instead of counts.
- Maximum Size Subarray Sum Equals k (LC 325): store the earliest index per prefix value and maximize j - i instead of counting.
- Binary Subarrays With Sum (LC 930): the all-non-negative special case where a sliding window DOES work — explain why the constraint change re-enables it.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why does a sliding window fail here?
Sliding windows need monotonicity: growing the window must only increase the sum. With negative values the sum can fall as the window grows, so there is no rule for when to shrink — the prefix-sum map removes the need for any window at all.
Why seed the hashmap with {0: 1}?
The empty prefix (before index 0) has cumulative sum 0. Without recording it, a subarray like [1,2] with k = 3 in nums = [1,2,...] finds seen[3-3] = seen[0] missing and never counts windows that start at the array's beginning.
Why store counts rather than just 'seen before'?
Prefix values repeat when the array contains zeros or negatives. If prefix value P occurred three times before the current position, there are three distinct subarrays ending here that sum to k — a boolean would count one.