Subarray sum equals k: the prefix-sum and hash-map solution

In this article

1. Before you start
2. Why interviewers ask this
3. Subarray sum equals k from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

Why interviewers ask this

Subarray sum equals k is a standard screen because it has a slow answer everyone finds, a fast answer few derive, and a tempting wrong answer in the middle. The slow answer sums every subarray. The fast answer needs the idea that a range sum is a difference of two running totals, plus a hash map to count matches. The tempting wrong answer is the window technique from the longest substring without repeating characters problem.

The interviewer is watching whether you test your idea against a negative number before you code it. The question is reported in interviews at large tech companies, often as a variation: a multiple of k, a shortest length, or a rectangle in a grid. A weak answer stops at brute force or at the window. A strong answer names the prefix-sum identity, handles the empty prefix, and states the time and memory cost.

Subarray sum equals k from first principles

In plain words

Subarray

A subarray is a run of neighbouring elements of an array, taken in order with no gaps. An array of n numbers has n times n plus one, divided by two, non-empty subarrays.

Prefix sum

A prefix sum is the total of an array's first i elements, so the prefix sum for zero elements is zero. Python's accumulate function produces them with an optional starting value.

Think of a bank statement with a running balance. To find how much you spent between two dates, you do not add up each purchase. You subtract the earlier balance from the later one.

The analogy breaks if you only watch the balance fall. Deposits and withdrawals mix, as positive and negative numbers do in the array, so the balance can rise and fall.

Precisely, the elements after the first i, up to and including the j-th, sum to the prefix sum after j elements minus the prefix sum after i elements (P[j] minus P[i], with i smaller than j).

The running example is the array 3, 4, 7, 2, minus 3, 1, 4, 2 with k equal to 7. It has four subarrays that sum to 7.¹

Step 1: Brute force checks every subarray

Brute force tries every start and end and keeps the runs that sum to k. For an array of n numbers it makes n times n plus one, divided by two, sum checks, even when each sum is extended from the previous one instead of recomputed. The eight numbers of the example need 36 checks.¹

def brute(nums, k):
    count = 0
    for i in range(len(nums)):
        total = 0
        for j in range(i, len(nums)):
            total += nums[j]          # extend the run by one element
            if total == k:
                count += 1
    return count

The cost grows with the square of the length: a thousand numbers need 500,500 checks and a hundred thousand need 5,000,050,000.¹ That is why the question has a follow-up. Brute force is still worth writing first, because it gives a correct answer to test the fast one against.

The input is the array. The output is the count 4, found with 36 checks.

Step 2: Prefix sums turn a range sum into one subtraction

A prefix sum array stores the running total after each element, and the sum of any run is the difference of two entries. Put a zero in front, so the prefix sum after zero elements is zero. The example gives 0, 3, 7, 14, 16, 13, 14, 18, 20.¹ The run from the third to the fourth element, 7 and 2, equals 16 minus 7, which is 9.

That turns the problem around. A run ends at some position and sums to k when an earlier prefix sum equals the current prefix sum minus k. In the example, the prefix sum 14 appears twice, and 14 minus 7 is 7, which is an earlier prefix sum, so both runs ending at those points are counted.¹ Two prefix sums that differ by k bracket a subarray that sums to k: P2 minus P0, P3 minus P2, P6 minus P2 and P8 minus P5 all equal 7, so four runs sum to 7. The prefix sum article calls these inclusive scans.

The input is the array. The output is the list of prefix sums, built in one pass.

Text description of the diagram

• The prefix sums after zero to eight numbers are 0, 3, 7, 14, 16, 13, 14, 18 and 20.
• P2 minus P0, P3 minus P2, P6 minus P2 and P8 minus P5 all equal 7, so four runs sum to 7.
• Two prefix sums that differ by k bracket a run that sums to k.

Step 3: A sliding window fails once a number can be negative

A sliding window cannot count subarrays that sum to k when the array has negative numbers, because the running total no longer moves one way. The window rule is: add the new element, and while the total is above k, drop elements from the left. That is correct only if dropping an element always lowers the total, which needs every number to be positive. Zeros break it too, because dropping a 0 changes nothing: on 0, 0 with k equal to 0 the window finds 2 runs but there are 3, and on 1, 0, 1 with k equal to 1 it finds 3 but there are 4.¹

On the example the window code returned 2 instead of 4. On the array 1, minus 1, 1 with k equal to 1 it returned 2 where the true count is 3.¹ In 2,000 random arrays with values from minus 5 to 5 (seed 0), the window count was wrong on 939 arrays, 931 of them containing a negative number (1,685 of the 2,000 arrays did), and every wrong answer was an undercount; the other 8 had zeros.

The prefix-sum method always matched brute force.¹ With only zeros and positives (values 0 to 5, seed 1, k from 0 to 12) the window was wrong on 296 of 2,000 arrays, and with values 1 to 5 on none.¹ A window is still the right tool for the shortest run with a sum of at least a target, which stays correct when the array has zeros.

The input is an array with a negative number. The output shows the window undercounting, which is why the next step uses prefix sums.

Step 4: Count earlier prefix sums in a hash map

A hash map of prefix sums lets each step count its matching runs in constant time on average. Keep a running prefix and a map from each prefix value to how many times it has been seen. At each element, add it to the prefix, add the map's count for prefix minus k to the answer, then record the new prefix.

def subarray_sum(nums, k):
    seen = {0: 1}                     # the empty prefix, seen once
    total = 0
    count = 0
    for x in nums:
        total += x
        count += seen.get(total - k, 0)
        seen[total] = seen.get(total, 0) + 1
    return count

The Python documentation lists getting and setting a dictionary item as constant time, as an average case that assumes a hash function good enough to keep collisions uncommon. The loop does one lookup and one update per element, so the total is linear.

The input is the array. The output is the count, from one pass.

Step 5: Seed the map with the empty prefix

Starting the map with the prefix sum 0 seen once is what counts the subarrays that begin at the first element. A run from the first element through the j-th sums to the prefix after j elements. It matches when the prefix minus k is zero, and zero must already be in the map. Leaving the seed out is the most common bug: the code then misses every run that starts at the start.

In the example the second element brings the prefix to 7, and 7 minus 7 is 0, so the map's seed counts the run 3, 4.¹ Update the map after the lookup, not before, or a run of length zero would count when k is zero.

The input is the loop of Step 4. The output is the complete method, correct for negative numbers and for runs that start at the first element.

1 · All subarrays2 · Prefix sums3 · No window4 · Hash map5 · Zero seedReplay

Step-by-step description

1. Brute force sums every subarray: 36 checks for 8 numbers.
2. A range sum becomes one subtraction of two prefix sums.
3. A sliding window fails once a number can be negative.
4. Count how often each earlier prefix sum occurred.
5. Start the map with prefix 0 seen once.

• Checking every subarray of eight numbers takes 36 sums.
• A sliding window fails once the array holds a negative number.
• The hash map starts with the prefix sum zero seen once.

Worked example

The four runs are 3 and 4; 7 alone; 7, 2, minus 3 and 1; and 1, 4 and 2.¹ A sliding window finds only 3, 4 and 7 and misses two runs: 7, 2, minus 3 and 1, and also 1, 4 and 2, which has no negative number in it. After the negative number the total never rises above 7 again, so the window never shrinks back to the 1 and the later runs are never reached.¹

The grid is a 3 by 4 array of numbers, with the six cells of the rectangle in the second and third rows, columns two to four, counting from 1, shown in brackets.

A 2D prefix sum is a table whose entry at a row and column holds the sum of the grid above and to the left of it. Adding the bottom right, then subtracting the strip above and the strip to the left, then adding back the overlap, is inclusion and exclusion. The same table in graphics is called a summed-area table. Summing the six cells directly gave the same 14.¹

Trade-offs and edge cases

The hash-map method is linear in time and in memory, and its limits are worth stating.

• Memory. The map holds up to one entry per distinct prefix sum, so extra space is up to the array length. Brute force needs no extra space but quadratic time.
• Worst-case hashing. The dictionary cost is an average. The Python documentation says that if every key hashes to the same value each operation becomes linear, which would make the method quadratic.
• Integer width. In a language with fixed-width integers the running prefix can overflow on large inputs. Use a 64-bit type.
• It counts, it does not list. To return the runs, store indices in the map instead of counts.
• Different questions, different tools. Counting subarrays that sum to k allows negatives and uses prefix sums. The shortest run with a sum of at least a target uses a window, because the numbers are non-negative. For the example 2, 3, 1, 2, 4, 3 and target 7 the answer is 2.¹

Text description of the diagram

• Counting subarrays that sum to k allows negatives and uses prefix sums.
• The shortest subarray with sum at least a target uses a sliding window with non-negative numbers.
• A rectangle sum takes constant time after the 2D prefix table is built.

How to answer it in an interview

The spoken structure is: brute force first, then the identity, then the map and its seed, then the window trap, then a test.

Common mistakes

• "Use a sliding window, it is linear" (wrong). It assumes every number is positive, and zeros break it too; with a negative it returned 2 where the count is 4 (right: use prefix sums and a map).
• "Store only whether a prefix was seen" (wrong). Several earlier prefixes can share a value, and each one is a different run (right: store counts).
• "Start with an empty map" (wrong). Runs that begin at the first element are then missed (right: seed the map with zero seen once).
• "Record the prefix before the lookup" (wrong). When k is zero this counts an empty run (right: look up first, then record).
• "The map makes it constant memory" (wrong). It holds up to one entry per distinct prefix (right: say linear extra space).

Follow-up questions

How do you check for a subarray of at least two elements whose sum is a multiple of k?

Store the first index at which each prefix sum modulo k occurred. When the same remainder appears again at least two positions later, the run between them sums to a multiple of k. On 23, 2, 4, 6, 7 with k equal to 6 the answer is yes, because 2 and 4 sum to 6.¹

How do you find the shortest subarray whose sum is at least a target?

Use a sliding window when every number is non-negative: grow the end, and shrink the start while the sum still meets the target, recording the shortest length. On 2, 3, 1, 2, 4, 3 with target 7 the shortest run has length 2. With negative numbers the window fails and a different method is needed.

What is a 2D prefix sum, and how does it give a rectangle sum?

It is a table where each entry holds the sum of the grid up to and including that row and column, built in one pass. A rectangle sum then takes four lookups: bottom right, minus above, minus left, plus the overlap. Building the table costs time proportional to the grid size, and each query is constant time.

What if the numbers arrive as a stream you cannot store?

The hash-map method still works, because it needs only the running prefix and the map, not the array. Memory grows with the number of distinct prefix sums, so a very long stream needs a bound or a different design. See the system design hub for streaming trade-offs, and Python interview questions for the dictionary behaviours the code relies on.

How do you find a submatrix whose row sums equal its column sums?

Build a row prefix table and a column prefix table, so the sum of any stretch of a row or a column takes constant time. Then try each choice of top-left and bottom-right corner and compare the row sums and column sums of that block. On the grid 1, 2, 3 / 3, 1, 2 / 2, 3, 1 the whole grid qualifies, because every row and every column sums to 6; the same grid has 10 qualifying blocks in all.¹ This is a different problem from counting runs that sum to k: it still uses prefix sums, but the hash map is not what it needs.

Sources

1. Time complexity of built-in types (dict section), Python 3 documentation — Python Software Foundation (page shows last updated Oct 24, 2026), 24 Oct 2026
2. itertools.accumulate, Python 3 documentation — Python Software Foundation (page shows last updated Oct 24, 2026), 24 Oct 2026
3. Prefix sum — Wikipedia (page last edited 14 October 2026), 14 Oct 2026
4. Summed-area table — Wikipedia (page last edited 1 September 2026; cites Crow 1984, SIGGRAPH '84), 1 Sep 2026