Free lesson · DSA Mastery - Interview Prep, End to End

Subarray Sum Equals K

Medium9 min readdsaprefix-sum

Subarray Sum Equals K

Subarray Sum Equals K is the most important problem in this module, and one of the most important in the entire course. It's the canonical prefix sum + hash map problem, and it's a perfect three-approach showcase: the brute force checks every subarray (O(n²) or O(n³) naively), the prefix-sum array removes the inner summation but is still O(n²), and the optimal solution adds a hash map to find the "complement" prefix in O(1) - collapsing the whole thing to O(n). That final leap ties directly back to the complement-lookup pattern from Two Sum.

Watching the approaches progress makes the optimal solution feel inevitable rather than magical - and it surfaces the subtle {0: 1} seed that trips up most people on their first attempt.

The Problem

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

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

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

Explanation: The subarrays [1,1] (indices 0-1) and [1,1] (indices 1-2) both sum to 2.

Example 2:

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

Explanation: [1, 2] (sum 3) and [3] (sum 3).

Constraints:

• 1 <= nums.length <= 2 * 10^4
• -1000 <= nums[i] <= 1000
• -10^7 <= k <= 10^7

Approaches Overview

A note on sliding window: it's tempting, but it does not work here because nums can contain negatives, so growing a window doesn't grow the sum monotonically. Sliding window is only valid when all numbers are positive. The general tool is prefix sum + hash map.

Approach 1: Brute Force

The Idea

Consider every subarray [i..j], sum it, and count those equal to k. The cleanest version fixes a start i, then extends j rightward maintaining a running sum - so it's O(n²), not O(n³).

Logic Flowchart

graph TD
    A["count = 0"] --> B["For start i = 0 to n-1"]
    B --> C["sum = 0"]
    C --> D["For end j = i to n-1"]
    D --> E["sum += nums[j]"]
    E --> F{"sum == k?"}
    F -->|Yes| G["count++"]
    F -->|No| H["continue"]
    G --> I{"More j?"}
    H --> I
    I -->|Yes| D
    I -->|No| J{"More i?"}
    J -->|Yes| B
    J -->|No| K["Return count"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style D fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style E fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style F fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style G fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style H fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style I fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style J fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style K fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the brute-force approach. For each start index, we extend the end index rightward, maintaining a running sum of the subarray. Each time the running sum equals k, we increment the count. The two nested loops make this quadratic.

Code

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

This Java code fixes each start index and extends the end index, accumulating a running subarray sum. Whenever the sum equals k, it counts that subarray. The nested loops give quadratic time.

Complexity

Time: O(n²) - every (start, end) pair, with O(1) incremental sum. Space: O(1).

Quadratic is too slow for n up to 2×10^4 (4×10^8 operations). The next step formalizes the running sum as a prefix array - which doesn't fix the quadratic yet, but sets up the insight that does.

Approach 2: Prefix Sum Array

The Idea

Precompute prefix sums P, where P[i] is the sum of the first i elements. The sum of subarray [i..j-1] is P[j] - P[i]. We still check all pairs (i, j) with i < j and count where P[j] - P[i] == k. This separates "computing sums" from "comparing them," which is the conceptual bridge to the hash-map version - but on its own it's still O(n²).

Logic Flowchart

graph TD
    A["Build P[]: P[i] = sum of first i elements"] --> B["count = 0"]
    B --> C["For j = 1 to n"]
    C --> D["For i = 0 to j-1"]
    D --> E{"P[j] - P[i] == k?"}
    E -->|Yes| F["count++"]
    E -->|No| G["continue"]
    F --> H{"More pairs?"}
    G --> H
    H -->|Yes| C
    H -->|No| I["Return count"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style D fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style E fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style F fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style G fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style H fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style I fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the prefix-sum-array approach. We precompute prefix sums, then for each end index we check every earlier prefix, counting pairs whose difference equals k. The sum of any subarray is now a constant-time subtraction, but checking all pairs is still quadratic.

Code

public static int subarraySumPrefixArray(int[] nums, int k) {
    int n = nums.length;
    int[] P = new int[n + 1];
    for (int i = 0; i < n; i++) P[i + 1] = P[i] + nums[i];

    int count = 0;
    for (int j = 1; j <= n; j++) {
        for (int i = 0; i < j; i++) {
            if (P[j] - P[i] == k) count++;
        }
    }
    return count;
}

This Java code builds a prefix-sum array, then counts pairs of prefix values whose difference equals k. Each subarray sum is now a subtraction, but the double loop over prefix pairs remains quadratic.

Complexity

Time: O(n²) - all prefix pairs. Space: O(n) - the prefix array.

Here's the key observation that breaks the quadratic: for each P[j], we're searching earlier prefixes for one equal to P[j] - k. That's a lookup - exactly what a hash map does in O(1). This is the Two Sum complement idea: the "complement" is P[j] - k.

Approach 3: Prefix Sum + Hash Map - Optimal

The Idea

Scan once, maintaining a running prefix sum. Keep a hash map from prefix-sum value → how many times it has occurred. For the current running sum, the number of subarrays ending here with sum k equals the count of earlier prefixes equal to running - k. Add that to the answer, then record the current running sum.

Seed the map with {0: 1} for the empty prefix. If a subarray from index 0 sums to k, then running = k and running - k = 0 - which must already be in the map. Forgetting this seed is the single most common bug.

Logic Flowchart

graph TD
    A["map = {0: 1}<br/>running = 0, count = 0"] --> B["For each num in nums"]
    B --> C["running += num"]
    C --> D{"(running - k) in map?"}
    D -->|Yes| E["count += map[running - k]"]
    D -->|No| F["no match"]
    E --> G["map[running]++"]
    F --> G
    G --> H{"More?"}
    H -->|Yes| B
    H -->|No| I["Return count"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style G fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style H fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style I fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the optimal approach. We seed the map with prefix sum zero seen once. For each element, we update the running sum, then add to the answer the number of times running minus k has appeared as a prefix sum, then record the current running sum. Looking up before recording prevents counting an empty subarray.

Code

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

    int running = 0, count = 0;
    for (int num : nums) {
        running += num;
        count += prefixCount.getOrDefault(running - k, 0);
        prefixCount.merge(running, 1, Integer::sum);
    }
    return count;
}

// Usage:
// System.out.println(subarraySum(new int[]{1, 1, 1}, 2));  // 2
// System.out.println(subarraySum(new int[]{1, 2, 3}, 3));  // 2

This Java code seeds a hash map with prefix sum zero counted once. For each element, it updates the running sum, adds the count of running minus k to the answer, then increments the count for the current running sum. Looking up before recording prevents counting a zero-length subarray when k is zero.

Step-by-Step Walkthrough

A frame-by-frame trace on nums = [1, 1, 1], k = 2. Each frame shows running, the complement looked up, the count added, and the map state after recording:

graph LR
    F0["Frame 0 (seed)<br/>map={0:1}<br/>running=0, count=0"]
    F1["Frame 1: num=1<br/>running=1<br/>look up 1-2=-1: absent<br/>count=0<br/>map={0:1, 1:1}"]
    F2["Frame 2: num=1<br/>running=2<br/>look up 2-2=0: found 1<br/>count=1<br/>map={0:1, 1:1, 2:1}"]
    F3["Frame 3: num=1<br/>running=3<br/>look up 3-2=1: found 1<br/>count=2<br/>map={0:1, 1:1, 2:1, 3:1}"]
    F0 --> F1 --> F2 --> F3

    style F0 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F1 fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough traces the optimal approach on one, one, one with k equal to two. The map is seeded with prefix sum zero. At running sum one, the complement minus one is absent. At running sum two, the complement zero is found once, so count becomes one - this is the subarray of the first two ones. At running sum three, the complement one is found once, count becomes two - the subarray of the last two ones.

Result: 2.

Complexity

Time: O(n) - one pass, O(1) hash operations. Space: O(n) - up to n distinct prefix sums in the map.

Complexity Comparison

The progression is the lesson: brute force does redundant summation; the prefix array fixes the summation but still searches all pairs; the hash map turns that search into an O(1) lookup. The "search earlier prefixes for a complement" insight is identical to Two Sum - only the target (running - k) differs.

Variations & Follow-ups

What if all numbers were positive?

Then sliding window also works (O(n) time, O(1) space) because the sum grows monotonically. With negatives possible, prefix sum + hash map is the general solution. Spotting this distinction is a key interview signal.

What if you wanted the longest (or shortest) subarray summing to k?

Store prefix sum → earliest index instead of a count. Then the length ending at i with sum k is i - map[running - k]; track the max. (Maximum Size Subarray Sum Equals k, LeetCode #325.)

What about Subarray Sums Divisible by K?

The next topic - same skeleton, but the map keys on running mod k instead of running.

What about overflow?

For these constraints (values ±1000, length 2×10^4), the running sum is at most 2×10^7 - fits in int. For larger inputs, use long.

What about edge cases?

• k = 0: Counts subarrays summing to 0. The seed and lookup-before-record order handle it (no empty-subarray false positives).
• All zeros, k = 0: The repeated prefix sum 0 accumulates counts, growing the answer correctly.
• No subarray sums to k: Returns 0. Negative k: Handled - the complement works with negatives.

Common Interview Pitfalls

• Forgetting to seed {0: 1}. Undercounts every subarray starting at index 0. The #1 bug.
• Recording before looking up. Look up running - k first, then record running; reversing can falsely count a zero-length subarray when k = 0.
• Trying sliding window with negatives. Sliding window assumes monotonic growth, which negatives break.
• Storing indices instead of counts. For the count problem, store counts. (Index storage is for the longest/shortest variant.)

Why This Problem Matters

Subarray Sum Equals K is the archetype of prefix sum + hash map, and the three-approach climb makes the optimal insight feel earned. The realization - "a subarray with sum k corresponds to two prefix sums differing by k, so search for the complement" - is one of the most reused ideas in all of algorithms.

It generalizes immediately: Subarray Sums Divisible by K (key on running mod k), Continuous Subarray Sum (remainder + earliest index), Contiguous Array (re-encode 0 as −1), Binary Subarrays With Sum, and Path Sum III in trees (Section 22). The deeper lesson: transform "find a subarray with property P" into "find two prefix values whose difference has property P," then use a hash map for O(1) complement lookup. Once you see this transformation, an entire class of O(n²)-looking problems collapses to O(n).

The next topic, Subarray Sums Divisible by K, applies this exact skeleton with a modulo twist.

Back to DSA Mastery - Interview Prep, End to End