Prefix Sum — Subarray Sum Equals K

↗ LeetCode: Subarray Sum Equals K · Medium · pattern chapter →

Asked atMetaAmazonGoogleBloomberg

Given an integer array nums (may contain negatives) and integer k, return the number of contiguous subarrays whose sum equals k.

Example 1 — nums = [1,1,1], k = 2 → 2 (the two [1,1] subarrays) Example 2 — nums = [1,2,3], k = 3 → 2 ([1,2] and [3]) Example 3 — nums = [1,-1,0], k = 0 → 3 ([1,-1], [0], [1,-1,0])

Constraints — 1 ≤ n ≤ 2·10⁴; -10³ ≤ nums[i] ≤ 10³. Brute enumerates every subarray in O(n²) = 4·10⁸ ops at n=2·10⁴ (borderline TLE). Prefix-sum + hashmap of complements is O(n) = 2·10⁴ ops = <2 ms.

Progressive Hints

Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.

---

⏱️Interview timer00:00

Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.

Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.

Approach 1 — Brute force (all subarrays)

Intuition. Enumerate every subarray [i..j]; sum it; count those equal to k.

int subarraySumBrute(int[] nums, int k) {
    int count = 0, n = nums.length;
    for (int i = 0; i < n; i++) {
        int s = 0;
        for (int j = i; j < n; j++) {
            s += nums[j];
            if (s == k) count++;
        }
    }
    return count;
}

Execution Trace

Brute — nums=[1,1,1], k=2: enumerate all 6 subarrays

Step 1 / 5[1] sum 1 ≠ 2

Complexity — Time O(n²) with the running sum trick; O(n³) without; Space O(1).

---

Approach 2 — Prefix sums (still O(n²), but sets up the optimization)

Insight from brute. If P[i] = sum of nums[0..i-1], then sum(nums[i..j]) = P[j+1] - P[i]. The brute-force question becomes: how many prefix pairs (a, b) have P[b] - P[a] = k?

int subarraySumPrefix(int[] nums, int k) {
    int n = nums.length, count = 0;
    int[] P = new int[n + 1];
    for (int i = 0; i < n; i++) P[i + 1] = P[i] + nums[i];
    for (int a = 0; a <= n; a++)
        for (int b = a + 1; b <= n; b++)
            if (P[b] - P[a] == k) count++;
    return count;
}

Not better asymptotically, but the reframing enables Approach 3.

---

Approach 3 — Prefix sums + hash map (one pass)

Insight from prefix. For each running prefix P[j], the question "how many earlier prefixes P[i] satisfy P[j] − P[i] = k?" is equivalent to "how many earlier prefixes equal P[j] − k?" — an O(1) hash lookup.

Seed the map with {0: 1} so a prefix that itself equals k counts as one subarray (from index 0).

Trap. Don't return the number of prefix values seen — return the count of times each prefix value was seen, because two different starts can produce the same prefix.

int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    count.put(0, 1);
    int prefix = 0, ans = 0;
    for (int x : nums) {
        prefix += x;
        ans += count.getOrDefault(prefix - k, 0);
        count.merge(prefix, 1, Integer::sum);
    }
    return ans;
}

Execution Trace

Prefix + hash map — nums=[1,1,1], k=2

Step 1 / 3seen[-1]=0 miss

Complexity — Time O(n) amortized; Space O(n) for the map. Optimal.

---

Try it yourself

Complexity summary

Approach	Time	Space
Brute force	O(n²)	O(1)
Prefix sum only	O(n²)	O(n)
Prefix + hash map	O(n)	O(n)

When to use which

• Cold interview → walk brute → prefix reframing → hash map.
• Interviewer probes "what if all values are positive?" → sliding window would work in O(n), O(1) space. But negatives break sliding window — this is why hash-map prefix is the general answer.

✨AI Study CompanionBeta

Related problems (same ladder applies)

• Subarray Sums Divisible by K — hash prefix % k
• Continuous Subarray Sum — same but requires length ≥ 2
• Contiguous Array — map 0→-1, then it's "sum equals 0"
• Binary Subarrays With Sum — same skeleton

Was this page helpful?

📚 Related problems

• → Subarray Sums Divisible By K
• → Car Pooling
• → Contiguous Array