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

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.

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.

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.

Run it in Python

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.

subarray_sum.pyPython 3
Output
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