Subarray Sum Equals K: Prefix Sums That Count in O(n) Time

Brute force checks every start-end pair and dies at O(n²) — fine for a whiteboard toy, fatal at a million rows. The prefix-sum ledger turns each position into one hashmap lookup, so the whole array resolves in a single pass. You'll build the running-sum map, count balance-minus-k sightings, and handle zeros and negatives without breaking stride. One pass. Zero pairs enumerated.

Problem Walkthrough — Prefix Algebra Does the Work

LeetCode 560: array nums (|nums| ≤ 2×10⁴, values −1000..1000), integer k (−10⁷..10⁷). Count contiguous subarrays summing to exactly k. Negatives are legal — that single fact eliminates half the candidate approaches.

Define prefix running[i] = nums[0]+...+nums[i−1] with running[0] = 0. Subarray (i..j−1) sums to k exactly when running[j] − running[i] = k. So when the running total is R, every earlier prefix equal to R − k closes one valid subarray ending here.

Example [1,2,3], k=3: running visits 0,1,3,6. At R=3, complement 0 seen once → [1,2]. At R=6, complement 3 seen once → [3]. Total 2. Example [1,1,1], k=2 → 2 ([0..1],[1..2]).

Brute Force and the Window Trap

Brute force enumerates all O(n²) (start, end) pairs and sums each — O(n²) time even with incremental sums, O(1) space. At n = 2×10⁴ that's ~2×10⁸ pairs. TLE by two orders of magnitude.

Sliding window looks like O(n) salvation but is incorrect: shrinking the left edge when the sum exceeds k assumes elements are non-negative. With −1000 in range, shrinking can discard the very prefix that a later negative would complete. It passes all-positive samples and fails hidden negatives deterministically.

Both are worth naming in interviews ('brute force is O(n²), window needs non-negatives which we don't have') — then never write them.

Optimal Approach — Prefix Sums Plus Hashmap

One pass with a running total and a frequency map of prefixes seen so far. Seed {0: 1} — the empty prefix exists once. Per element: extend running, add prefix_counts[running − k] to the answer, then record running in the map.

Why the order matters: counting before recording prevents a prefix from matching itself (which would conjure zero-length subarrays). Why the seed matters: a subarray starting at index 0 has prefix[i] = 0, and 0 must already be in the map.

Trace [1,−1,0], k=0: seed {0:1}. x=1: R=1, comp 1 → 0, map {0:1,1:1}. x=−1: R=0, comp 0 → +1 (total 1: [1,−1]), map {0:2,1:1}. x=0: R=0, comp 0 → +2 (total 3: [1,−1],[1,−1,0],[0]). Correct.

The Prefix-Sum Solution in Full Python

Nine lines of logic: seed, loop, extend, count complement, record. defaultdict(int) returns 0 for unseen complements so no membership tests clutter the hot loop. The running total absorbs negatives naturally — no branches, no windows.

The __main__ block pins five cases: both canonical samples, the zero-sum trio ([1,−1,0] → 3, catches self-match ordering bugs), the singleton-from-zero (catches missing seed), and a negative sandwich (catches window refugees).

from collections import defaultdict
from typing import List


class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        """Prefix sums + hashmap: O(n) time, O(n) space. Handles negatives."""
        prefix_counts: dict[int, int] = defaultdict(int)
        prefix_counts[0] = 1  # empty prefix seen once
        running = 0
        total = 0
        for x in nums:
            running += x
            total += prefix_counts[running - k]
            prefix_counts[running] += 1
        return total


if __name__ == "__main__":
    s = Solution()
    assert s.subarraySum([1, 1, 1], 2) == 2
    assert s.subarraySum([1, 2, 3], 3) == 2
    assert s.subarraySum([1, -1, 0], 0) == 3
    assert s.subarraySum([1], 1) == 1
    assert s.subarraySum([-1, 2, -1], 0) == 1
    print("all checks passed")

Negative Numbers, k = 0 and Overlapping Subarrays

All zeros, k=0, n=m: answer is m(m+1)/2 subarrays — verifies combinatorial counting, not just detection. Single element equal to k → 1 (seed check); single element unequal → 0. Large k with no match → 0, exercising the defaultdict miss path.

Negative-heavy: [−1,−1,1], k=−1 → 3 ([−1]×2 initial... precisely: [0..0],[1..1],[0..2]). Alternating [1,−1,1,−1], k=0 → 4. These break any residual window logic instantly.

Overflow is a non-issue in Python; in Java/C++ use long for running (n × 1000 fits int, but k ranges to 10⁷ — the subtraction stays safe in 64-bit). Empty array → 0 by loop vacuity.

Complexity — Why O(n) / O(n) Is the Floor

Prefix + hashmap: O(n) time — one lookup and one insert per element, both O(1) average. O(n) space for up to n+1 distinct prefix sums. Handles the full constraint range including negatives with zero extra logic.

Brute force: O(n²) time, O(1) space — dead at 2×10⁴. Sliding window: O(n)/O(1) but incorrect on negatives — disqualified, not just slower. Divide and conquer: O(n log n)/O(log n), correct yet strictly worse on constants and code size.

Space reduction below O(n) isn't available for exact counting with arbitrary integers — say so if asked, and name the bounded-range exception (coordinate compression + Fenwick) to show you know where the floor is.