Skip to main content
DSA patterns

Subarray Sum Equals K

mediumPrefix sum Must-doMetaRazorpayPhonePe

Problem statement

You're given a list of integers nums and a target integer k. Count how many contiguous stretches of nums (subarrays) add up to exactly k.

nums can contain negative values, so a running total can go down as well as up — think of it as counting how many time windows in a stream of daily profit-and-loss numbers, or request-count deltas, net out to exactly a target change.

Examples

Example 1

Input: nums = [1, 1, 1], k = 2

Output: 2

Explanation: The subarrays [1, 1] (indices 0–1) and [1, 1] (indices

Example 2

Input: nums = [1, 2, 3], k = 3

Output: 2

Explanation: The subarrays [1, 2] (indices 0–1) and [3] (index 2)

Hints

Hint 1: Checking every subarray directly by adding up its elements works — but count how many subarrays a list of n elements has, and how that grows as n grows.

Approach

Optimal: Prefix sum counted in a hash map

Intuition

The brute force keeps re-deriving "does this subarray sum to k?" one subarray at a time. Flip the question around: keep a single running total as you scan left to right, and ask instead, "how many earlier positions had a running total that was exactly k less than the one I have right now?" — because the difference between any two running totals is the sum of the subarray between them. Counting how often each running-total value has occurred, in a hash map, answers that question in O(1) per element instead of rescanning.

The map starts with {0: 1} — not empty — because a subarray that starts at index 0 needs to match against the sum "before anything has been added yet", which is 0. Without that seed entry, valid subarrays starting right at the beginning of nums would never be counted.

Steps

  1. Create a hash map prefixCount with one entry: {0: 1}.
  2. Set curSum = 0 and count = 0.
  3. For each value x in nums:
    • Add x to curSum.
    • Let need = curSum - k. If need is a key in prefixCount, add its count to count — that many earlier positions form a valid subarray ending here.
    • Increment prefixCount[curSum] by 1 (inserting it with count 1 if it wasn't there yet).
  4. After the loop, return count.

Dry run

nums = [1, 1, 1], k = 2. Start with prefixCount = {0: 1}, curSum = 0, count = 0.

x curSum need = curSum - k matches found count after prefixCount after
1 1 -1 0 (not in map) 0 {0:1, 1:1}
1 2 0 1 (prefixCount[0]) 1 {0:1, 1:1, 2:1}
1 3 1 1 (prefixCount[1]) 2 {0:1, 1:1, 2:1, 3:1}

Final count = 2, matching the example — and matching the brute force's result, but in one pass instead of a double loop.

Edge cases: if k = 0 and nums contains no zero-sum subarray, need never matches an existing key beyond what's expected, and count stays correct at 0. Negative numbers are handled without any special case, since curSum and need are plain integers that can go up or down — nothing here assumes the running total only increases.

Complexity

Time O(n) - each element is visited exactly once. Looking up and updating a hash map entry are both O(1) on average, so the whole pass costs O(n) instead of the brute force's O(n²). For 20,000 elements that's 20,000 steps instead of roughly 200 million — the difference that actually matters once `nums` gets large.

Space O(n) - the hash map can end up holding one entry per distinct running total seen, which is at most `n + 1` (including the starting `0`).

class Solution:
    def subarraySum(self, nums: list[int], k: int) -> int:
        prefix_count = {0: 1}
        cur_sum = 0
        count = 0
        for x in nums:
            cur_sum += x
            need = cur_sum - k
            if need in prefix_count:
                count += prefix_count[need]
            prefix_count[cur_sum] = prefix_count.get(cur_sum, 0) + 1
        return count


if __name__ == "__main__":
    print(Solution().subarraySum([1, 1, 1], 2))  # 2
    print(Solution().subarraySum([1, 2, 3], 3))  # 2
RecapThe whole problem in a few lines, for the night before
  • Spot it: "count contiguous subarrays that sum to a target k", especially when the array can contain negative numbers
  • Idea: track a running sum; keep a hash map counting how often each running-sum value has occurred; for each element, add prefixCount[curSum - k] to the answer, seeded with {0: 1}
  • Cost: O(n) time, O(n) space (running-sum brute force: O(n²) time, O(1) space; re-summing from scratch: O(n³))
  • Trap: forgetting to seed the map with {0: 1} silently under-counts every subarray that starts at index 0
  • Remember: negative values rule out a sliding window here — the running sum isn't monotonic, which is exactly why the hash-map trick exists

Interview follow-ups

  • What if you needed the actual subarrays, not just how many there are?

    Instead of counting occurrences of each prefix sum, store the list of indices where each prefix sum occurred. When the current running total minus k matches a stored prefix sum, every one of those stored indices marks the start of a valid subarray ending at the current position. Time stays O(n) for the scan, but you now also pay for however many subarrays you actually report, and space grows to hold every index instead of just a count.

  • What if nums only ever contained non-negative integers — does anything change?

    The hash-map approach still works exactly as written, and stays O(n). What changes is that a sliding window becomes possible for closely related questions, like "count subarrays whose sum is at most k" or "find the shortest subarray with sum at least k", because with only non-negative values a running sum can only grow as the window's right edge moves and only shrink as the left edge moves — the monotonic behavior a two-pointer window depends on. This exact problem (counting subarrays with sum equal to k) still needs the hash-map trick either way, since "equal to" doesn't shrink or grow monotonically the way "at most" or "at least" does.

  • The array is a live, unbounded stream — you can't store the whole thing. How would you adapt this?

    The hash map of prefix-sum counts can still be kept incrementally, one value at a time, without ever storing the array itself — memory grows with the number of distinct prefix sums seen, not the length of the stream. If that map itself risks growing unbounded over a very long-running stream, the common trade is to expire old entries once you know subarrays older than some window can no longer matter for the query you actually need (e.g., "sum equals k within the last hour"), turning it into a bounded sliding-window variant of the same idea.

Frequently asked questions

Because a running total is compared against "the running total k steps back", and a subarray that starts at index 0 has nothing before it — its "before" total is 0. Seeding the map with {0: 1} means that case is handled the same way as every other position, with no special-cased if i == 0 branch. Try removing it mentally: nums = [2, -2], k = 0 would under-count, because the subarray [2, -2] (the whole array, matching against the empty prefix) would never be found.

A sliding window (as in Minimum Size Subarray Sum) relies on the window's sum changing predictably as you move its edges — usually because all values are non-negative, so extending the window can only increase the sum, and shrinking it can only decrease it. Here, nums can contain negative values, so growing the window doesn't guarantee the sum moves in one direction. That breaks the assumption a two-pointer window depends on, which is why this problem reaches for a hash map of prefix sums instead.

Because the improvement isn't in how many subarrays get checked — it's in how much work each check costs. The brute force re-adds every element of a subarray from scratch every time, which is the difference between O(n³) and O(n²) overall. Both the brute force and the "better" approach still examine every one of the n·(n+1)/2 subarrays; the hash-map optimal approach is the one that changes that, by answering "how many subarrays ending here sum to k?" without enumerating subarrays at all.

It's just a running total. prefix[i] is the sum of every element from the start of the array up through index i - 1. The reason it's useful is that the sum of any subarray nums[i..j] can be written as prefix[j+1] - prefix[i] — a single subtraction — instead of re-adding every element in that range each time you want to check it.

Counting how many time windows a cumulative metric returns to a specific value — net requests processed, a budget's running balance, a queue's net enqueue-minus-dequeue count — shows up whenever you're looking for periods where "nothing net changed" or "exactly a target amount changed". The prefix-sum-plus-hash-map pattern is the standard tool for counting that without rescanning the whole series for every window.