vizlearn

Subarray sum equals k

Interview QuestionsBy Updated

Carry a running sum and a dictionary of how often each running sum has been seen. A subarray ending here sums to k exactly when running − k appeared earlier — so the count is a lookup, not a search. O(n) time and space.

Overview

The problem

Count the number of contiguous subarrays whose elements sum to exactly k.

InputkCountThe subarrays
[1, 1, 1]22[1,1] at 0-1 and at 1-2
[1, 2, 3]32[1,2] and [3]
[1, -1, 0]03[1,-1], [0], [1,-1,0]
[3, 4, 7, 2, -3, 1, 4, 2]74Several

Negative numbers are allowed, and that single fact rules out the sliding window. This is the crux of the problem.

The brute force sums every subarray: O(n²) with running sums, O(n³) if the sum is recomputed each time. The intended solution is O(n).

Dicts, sets & hashingCoding problemMedium

Step through it

What to watch

  • The map counts occurrences, not positions — duplicates matter.
  • The lookup happens before the current sum is recorded.
  • Negative numbers are why a sliding window cannot be used.

Say this out loud

"Prefix sums in a dict. At each index I've got the running sum, and any earlier prefix equal to running minus k marks the start of a qualifying subarray. Seed the map with {0: 1} so subarrays starting at index 0 are counted. O(n)."

Subarray sum equals k

Count the contiguous subarrays that sum to k.

Run it

The prefix-sum count against brute force with both operation counts, the missing-seed bug failing on a one-element array, and the sliding window breaking on a negative number.

1Python
Output
2Python
Output
3Python
Output
4Python
Output

                

                

                    
Why the sliding window fails

                    
A sliding window works when growing it increases the sum and shrinking it decreases the sum — that monotonicity is what makes "too big, shrink from the left" a valid decision.
With negatives, the sum is not monotonic. On [1, -1, 1] with k = 1, a window whose sum is already 1 might still be extendable to another valid window, and a window whose sum is too large might become correct by growing. There is no correct rule for when to move the left pointer.
ConstraintTechnique
All positive, find a subarray with sum kSliding window, O(n)
All positive, minimum length with sum ≥ kSliding window, O(n)
Negatives allowed, count subarrays summing to kPrefix sums plus a hash map
Negatives allowed, maximum sumKadane's algorithm
Recognising which of those four you have been asked is most of the work.

                

                

                    
Prefix sums and the key identity

                    
Let prefix[i] be the sum of the first i elements. Then the sum of the subarray from index i to j−1 is prefix[j] - prefix[i].
So a subarray ending at j sums to k exactly when:
prefix[j] − prefix[i] = k  ⇒  prefix[i] = prefix[j] − k
Which turns the problem into: while scanning, count how many earlier prefix sums equal current - k. A dictionary of prefix-sum frequencies answers that in O(1).
5Python
Output
O(n) time and O(n) space.
counts[0] = 1 is the line everything hinges on. It represents the empty prefix, and it is what allows a subarray starting at index 0 to be counted. Without it, [1, 2, 3] with k = 3 finds only [3] and misses the leading [1, 2], because that subarray needs prefix[i] = 0 to exist.
The order also matters: count before inserting. Inserting running first would let a subarray of length zero match when k = 0.

                

                

                    
From a difference to a lookup

                    
Let P(i) be the sum of everything up to index i. The subarray from j+1 to i sums to P(i) − P(j), so it equals k exactly when P(j) = P(i) − k.
That converts "search backwards for a matching start" into "have I seen this value before?", which a dictionary answers in O(1). It is the same move as Two Sum — compute the thing you need rather than hunting for it.

                

                

                    
Why {0: 1} and not an empty map

                    
The empty prefix has sum 0, and it must be in the map before the loop starts. Otherwise a subarray beginning at index 0 — where running itself already equals k — has no earlier prefix to match against and is never counted.
Seeding with {0: 1} is the single most commonly missed line in this problem, and it fails on the simplest possible input: [k].

                

                

                    
Why not a sliding window

                    
A sliding window needs the sum to grow when the window grows, so shrinking from the left is a sound response to overshooting. With negative numbers that monotonicity is gone: extending the window can make the sum smaller, so there is nothing to slide on.
If the question guarantees all-positive values, say so and use the window — O(1) space instead of O(n). Noticing that the constraint changes the right answer is worth as much as the code.

                

                

                    
Tracing it

                    
[3, 4, 7, 2, -3, 1, 4, 2] with k = 7:
numrunningrunning - kFoundcounts after
—0——{0:1}
33−40{0:1, 3:1}
4701{0:1, 3:1, 7:1}
71471{…, 14:1}
21690{…, 16:1}
−31360{…, 13:1}
11471{…, 14:2}
418110{…, 18:1}
220131{…, 20:1}
Total: 4. The 14:2 entry is the reason a count is stored rather than a set — the same prefix sum recurring means several valid starting points, and a set would count only one of them.

                

                

                    
The variants

                    
Return a subarray rather than a count. Store the index of each prefix sum instead of its frequency, and return on the first match.
Longest subarray with sum k. Store the earliest index for each prefix sum — if s not in first: first[s] = i — so the span found is maximal.
Subarray sums divisible by k. Key the dictionary on running % k instead of running. Watch for Python's % returning non-negative results for negative operands, which is actually convenient here; in languages where it does not, normalise with ((r % k) + k) % k.
Binary subarrays with sum k, or "at most k" problems — these are usually sliding windows again, because the values are non-negative.
Contiguous array with equal 0s and 1s. Map 0 to −1 and find the longest subarray summing to 0 — the same technique with a substitution.
2D version: submatrix sum equals target. Fix a pair of rows, compress the columns between them into a 1D array, and run this algorithm. O(n²m).

                

                

                    
Edge cases

                    
CaseNote
k = 0Works; counts[0] = 1 and the count-before-insert order matter most here
All zeros, k = 0Answer is n(n+1)/2 — every subarray qualifies
Empty array0
Single element equal to k1
No subarray sums to k0
All negativeWorks — nothing assumes a sign
Large sumsPython integers are unbounded; other languages need care about overflow
[0, 0, 0] with k = 0 giving 6 is a good self-check: the dictionary reaches {0: 4} and contributes 1 + 2 + 3.

                

                

                    
What it is testing

                    
Do you notice the negatives? Reaching for a sliding window is the expected wrong turn, and identifying why it fails is the insight being probed.
Do you know the prefix-sum identity? sum(i..j) = prefix[j] - prefix[i] is the most reusable formula in array problems.
Do you initialise counts[0] = 1? The single most common bug, and it silently produces answers that are correct except at the start of the array.
Do you count before inserting? Reversing them breaks the k = 0 case.
Do you store counts rather than a set? Repeated prefix sums each contribute a subarray.
Can you adapt it? Longest-subarray and divisible-by-k variants follow from changing what the dictionary stores.

                

                

                    
Recap in one screen

                    
  • Negative values rule out a sliding window, because the sum is no longer monotonic in the window size.
  • Use prefix sums: a subarray ending here sums to k when an earlier prefix equals running - k.
  • A dictionary of prefix-sum frequencies answers that in O(1), giving O(n) overall.
  • Seed it with {0: 1} for the empty prefix, or subarrays starting at index 0 are missed.
  • Count first, then insert — and store frequencies, not a set.

                

            


        

    



How the code works
The prefix-sum count against brute force with both operation counts, the missing-seed bug failing on a one-element array, and the sliding window breaking on a negative number.
How the code works
  1. seen[0] = 1The empty prefix. Without it, a subarray starting at index 0 has no earlier prefix to match and is never counted — and [7] with k=7 returns 0.
  2. count += seen[running - k]Adds the number of times that prefix occurred, not one. Several earlier positions can produce the same running sum, and each is a distinct subarray.
  3. the lookup precedes seen[running] += 1Recording first would let the current prefix match itself when k is 0, counting an empty subarray that does not exist.
  4. sliding_windowKept to be broken. It needs the sum to rise monotonically as the window grows, which one negative number destroys — the last block shows it giving the wrong count.
Change one thing
  • Set k = 0 on an array containing a [2, -2] pair. The count includes it, which is why the lookup must come before the record.
  • Make every value positive and compare the window with the prefix map. Same answers, and the window uses O(1) space.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.


    



Check yourself
0 of 3
Answer without scrolling back up.
  1. Why is the prefix map seeded with {0: 1}?
  2. The map stores, for each prefix sum:
  3. Why can't a sliding window be used here?





 Cheat sheet
Subarray sum equals k
Carry a running sum and a dictionary of how often each running sum has been seen. A subarray ending here sums to k exactly when running − k appeared earlier — so the count is a lookup, not a search. O(n) time and space.
INTERVIEW · vizlearn.in/interview/subarray-sum-equals-k.html
More in Interview
InterviewWhen should you use a set instead of a list?InterviewWhat happens if you modify a collection while looping over it?InterviewMemoisation: caching with a dictionaryInterviewImplement a hash map from scratch
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact