Subarray Sum Equals K: Can You Solve It in 20 Minutes?

You've solved this problem before. You just haven't solved it in 20 minutes, live, while someone takes notes on everything you do.

Here's a real interview problem: Subarray Sum Equals K. Set a timer before reading further. The version where you read the walkthrough first doesn't count. That version is how you end up nodding in the debrief call wondering how it went so wrong.

Same problem. Completely different experience.

The Problem: Subarray Sum Equals K

Given an integer array nums and an integer k, return the total number of subarrays whose sum equals k.

Examples:

• nums = [1, 1, 1], k = 2 → 2
• nums = [1, 2, 3], k = 3 → 2

Set a 20-minute timer. Write a working solution before reading further.

---

Still reading? Come back when you've actually tried it. Skipping to the walkthrough is exactly how you end up surprised in a real interview.

---

Ask These Questions Before Writing Anything

Most candidates open an editor the moment the problem ends. Strong candidates ask questions first. These are not formalities. The answers change your entire approach.

• Can numbers be negative? Yes. This matters a lot.
• Can k be zero or negative? Yes.
• What's the input size? Up to 2 × 10⁴. O(n²) is borderline; O(n) is the target.
• Subarrays only, or subsequences too? Contiguous subarrays only.

If you skipped the negative-numbers question and went straight to coding, you almost certainly built the wrong solution. The interviewer just noted that. Not loudly. Just quietly, in the rubric.

Clarifying questions are scored explicitly at most companies. They are not small talk.

The Brute Force

Two nested loops: for each start index, extend rightward and track the running sum. Increment when it hits k.

def subarray_sum(nums: list[int], k: int) -> int:
    count = 0
    for i in range(len(nums)):
        total = 0
        for j in range(i, len(nums)):
            total += nums[j]
            if total == k:
                count += 1
    return count

O(n²) time, O(1) space. Correct. Write this down anyway. Getting to a correct O(n²) in two minutes is worth more than arriving at a wrong O(n) in five, and the interviewer knows it too.

The Trap That Catches Most Candidates

Your next instinct is sliding window. Variable-size window, shrink from the left when the sum overshoots k. O(n), elegant. You've seen it in three LeetCode editorials and it felt like magic every time.

It is wrong.

Sliding window works because adding elements grows the sum and removing elements shrinks it. That assumption collapses with negative numbers. With nums = [1, -1, 1, 1] and k = 2, a window that overshoots might need to grow to recover. The two-pointer logic has no mechanism for that. You'd be shrinking when you should be growing, blissfully unaware, submitting wrong answers with full confidence.

This is the difference between internalizing a pattern and memorizing its shape. Recognizing why it fails, before discarding it, is itself a signal the interviewer is looking for. Most candidates don't even get that far. They just submit the sliding window and wait.

The O(n) Solution: Prefix Sums

Define prefix[i] as the sum of nums[0..i]. A subarray nums[i..j] sums to k when:

prefix[j] - prefix[i-1] = k

Rearranged:

prefix[i-1] = prefix[j] - k

Scan left to right, tracking the running prefix sum. At each index, count how many previous prefix sums equal current - k. A hash map does the lookup in O(1).

from collections import defaultdict

def subarray_sum(nums: list[int], k: int) -> int:
    count = 0
    prefix = 0
    seen = defaultdict(int)
    seen[0] = 1  # the empty prefix before index 0

    for num in nums:
        prefix += num
        count += seen[prefix - k]
        seen[prefix] += 1

    return count

The seen[0] = 1 initialization handles subarrays starting at index 0. Without it, any valid subarray from the first element gets missed. This single line is responsible for more wrong answers than any other part of this problem. It looks optional. It is not. It produces a subtle bug that passes most test cases and fails exactly one, the one the interviewer tests manually after you say you're done.

O(n) time, O(n) space.

Score Yourself Against the Actual Rubric

Here is roughly what the interviewer is writing down. Not guessing. Writing.

• Asked about negative numbers before coding: positive signal on problem scoping
• Brute force in under five minutes: can execute, correct vocabulary
• Identified why sliding window fails: knows pattern preconditions, not just shape
• Arrived at prefix sum independently: demonstrates the core insight
• Included seen[0] = 1 without a prompt: real attention to edge cases
• Stated time and space complexity without being asked: communication above baseline

Full marks: you'd pass. Needed a nudge at the prefix sum step but ran with it: borderline, depends on how you responded to the hint. Submitted sliding window as final answer: the interviewer has a note that says you missed a key constraint. That note does not expire.

The honest self-test is not whether you got the right answer. It is whether you would have gotten there in 20 minutes, with someone watching, without this walkthrough.

---

If you want to find out for real, SpaceComplexity runs live voice mock interviews with a timer and rubric-based feedback on every dimension above.