Reader Solutions Reviewed: Subarray Sum

Canonical solution and common mistakes

Photo by Erik Mclean on Unsplash

Problem recap

You’re given an integer array nums and an integer k.
Return the number of contiguous subarrays whose sum is exactly k.

Example

• nums = [1, 2, 3, -2, 5], k = 3

There are 2 valid subarrays: [1, 2], [3].

---

Approach 1: Brute force, but with a running sum

The naïve approach is “all subarrays, sum each,” which is O(n^3), but you can upgrade that to O(n^2) by carrying a running sum inside the inner loop.

• Fix a start index i.

• Walk j from i to the end, maintaining current_sum += nums[j].

• Each time current_sum == k, increment a counter.

from typing import List

def subarray_sum_bruteforce(nums: List[int], k: int) -> int:
    count = 0
    n = len(nums)
    for i in range(n):
        current_sum = 0
        for j in range(i, n):
            current_sum += nums[j]
            if current_sum == k:
                count += 1
    return count

public int subarraySumBruteForce(int[] nums, int k) {
    int count = 0;
    for (int i = 0; i < nums.length; i++) {
        int currentSum = 0;
        for (int j = i; j < nums.length; j++) {
            currentSum += nums[j];
            if (currentSum == k) {
                count++;
            }
        }
    }
    return count;
}

Talking points:

• Time: O(n^2), space: O(1).

• Works fine with negatives because it does not rely on any ordering property.

Before reading on, can you think of a way to reuse some of this work to get to linear time?

---

Approach 2: The “expanding–shrinking window” that breaks with negatives

This is the most common incorrect approach.

The sliding window with two pointers works when all numbers are non‑negative:

• Keep start, end, and current_sum over nums[start:end).

• Expand end while current_sum < k.

• Shrink from start while current_sum > k.

• Check for current_sum == k along the way.

This relies critically on the fact that when all numbers are non‑negative:

• Increasing the window (move end right) never decreases the sum.

• Decreasing the window (move start right) never increases the sum.

So you never “miss” a candidate by shrinking or expanding.

Here’s an “only works when all elements are non‑negative” cautionary example:

// WARNING: Only correct if all nums[i] >= 0
public int subarraySumSlidingWindowNonNegative(int[] nums, int k) {
    int start = 0, currentSum = 0, count = 0;

    for (int end = 0; end < nums.length; end++) {
        currentSum += nums[end];

        while (start <= end && currentSum > k) {
            currentSum -= nums[start++];
        }

        if (currentSum == k) {
            count++;
        }
    }
    return count;
}

Why this fails with negatives

Give a concrete counterexample:

• nums = [3, 4, -2], k = 5.

Correct subarray is [3, 4, -2]. The window algorithm may shrink too early when current_sum > k, but the later negative value could have brought it back down to k.

Once you discard elements from the left, you cannot recover that subarray. The key invariant “sum only moves in one direction when expanding or shrinking” is broken by negative numbers.

General rule:

• Any time your algorithm decides ‘I can safely skip all longer windows starting here because the sum is already too big/small,’ it assumes monotonicity. Negatives destroy that.

If sliding window doesn’t work with negatives, what property must the real solution exploit instead?

---

Approach 3: Prefix sums + hash map (the correct O(n) running-sum solution)

Approach 1 is not wrong, just suboptimal.

You’ve discovered one kind of running sum. The final step is to recognize that you don’t actually need to restart the sum at every i. You can reuse the same running prefix sum for all i simultaneously if you store counts in a map.

• Let prefix[i] be the sum of nums[0..i].

• The sum of subarray nums[l..r] is prefix[r] - prefix[l-1].

• For a subarray ending at index i to have sum k, you need some earlier prefix sum prefix[j] such that:

\(prefix[i] - prefix[j] = k \Rightarrow prefix[j] = prefix[i] - k\)

So as you scan from left to right while maintaining a running prefix sum, you only need to know:

• How many times have you seen the value currentSum - k before?

That count equals the number of subarrays ending at the current index whose sum is k.

This works with negative numbers, positive numbers, and any mix, because it does not rely on monotonicity, only on the algebraic relationship between prefix sums.

Key implementation detail:

• Initialize the map with sum_frequency[0] = 1 so that when currentSum == k, you correctly count subarrays starting at index 0.

Canonical solutions

You can walk through nums = [1, 2, 3, -2, 5], k = 3 step‑by‑step with any of the following solutions to build intuition.

from typing import List
from collections import defaultdict

def subarray_sum(nums: List[int], k: int) -> int:
    freq = defaultdict(int)
    freq[0] = 1  # empty prefix

    current_sum = 0
    count = 0

    for x in nums:
        current_sum += x

        # number of previous prefixes we can pair with current_sum to get k
        need = current_sum - k
        count += freq[need]

        # record current prefix sum for future elements
        freq[current_sum] += 1

    return count 

Java

import java.util.HashMap;
import java.util.Map;

public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    freq.put(0, 1);  // empty prefix

    int currentSum = 0;
    int count = 0;

    for (int x : nums) {
        currentSum += x;

        int need = currentSum - k;
        count += freq.getOrDefault(need, 0);

        freq.put(currentSum, freq.getOrDefault(currentSum, 0) + 1);
    }

    return count;
}

C#

using System.Collections.Generic;

public int SubarraySum(int[] nums, int k) {
    var freq = new Dictionary<int, int>();
    freq[0] = 1;  // empty prefix

    int currentSum = 0;
    int count = 0;

    foreach (int x in nums) {
        currentSum += x;

        int need = currentSum - k;
        if (freq.TryGetValue(need, out int occ)) {
            count += occ;
        }

        if (freq.ContainsKey(currentSum)) {
            freq[currentSum]++;
        } else {
            freq[currentSum] = 1;
        }
    }

    return count;
}

TypeScript

export function subarraySum(nums: number[], k: number): number {
    const freq = new Map<number, number>();
    freq.set(0, 1);  // empty prefix

    let currentSum = 0;
    let count = 0;

    for (const x of nums) {
        currentSum += x;

        const need = currentSum - k;
        if (freq.has(need)) {
            count += freq.get(need)!;
        }

        freq.set(currentSum, (freq.get(currentSum) ?? 0) + 1);
    }

    return count;
} 

Complexity talking point: one pass, constant-time hash operations → O(n) time, O(n) space in the worst case.

---

“Running sum” vs “running window”

• “Running sum” just means you keep a cumulative total as you iterate; both the O(n^2) brute force and the O(n) prefix-sum+map use a running sum.

• The flawed pattern is not “running sum,” it is “sliding window that assumes ‘if my sum is already too big/small, I can discard this start index forever’.”

---

Other common reader mistakes

Using a set instead of counting frequencies

Some people get to the prefix-sum idea but stop at “I just need to know if currentSum - k exists in some set of previous sums.” That only tells you whether at least one subarray ending here sums to k.

But this problem asks for the count of subarrays. There may be multiple previous indices j1, j2, … with the same prefix sum currentSum - k, and each corresponds to a distinct subarray ending at the current index.

So a common bug is:

seen = set()
seen.add(0)
current_sum = 0
count = 0
for x in nums:
    current_sum += x
    if current_sum - k in seen:
        count += 1          # BUG: only adds 1 even if there are multiple matches
    seen.add(current_sum)

The fix is to store frequencies and add freq[currentSum - k] rather than just 1.

---

Forgetting to seed sum 0 in the map

Any correct prefix-sum + hash‑map solution needs:

freq = {0: 1}  # or equivalent in Java/C#/TS

right before the loop.

A subtle, off‑by‑one‑ish bug: initialize an empty map and only start recording prefix sums inside the loop.

What goes wrong:

• Consider subarrays that start at index 0.

• For such a subarray ending at index i, you have prefix[i] == k.

• In the map logic, you’re looking for prefix[i] - k == 0.

• If you never seeded sum_frequency[0] = 1, you’ll miss those subarrays entirely.

---

If you’re a paid subscriber, you also get a weekly long-form post and the option to request a private resume/LinkedIn review.

Next week’s long-form post is about strings and anagrams: sorted key vs. frequency tuple, prime product hashing trick, and interview traps.

Not paid yet? You can upgrade here:

---

© The Coding Interview Gym | paulepps.substack.com