SyntaxPilot
Courses/DSA and Coding Problems/Lesson 5

DSA and Coding Problems · Lesson 5 of 90 · 12 min

Prefix sums: subarray sum equals K

queued

These are the notes for DSA episode 5. The problem (LeetCode 560) asks how many subarrays add up to exactly k. Trying every subarray is O(n²). A sliding window looks faster but gives wrong answers when numbers can be negative. The fix is a prefix sum (a running balance) plus the HashMap from Two Sum: one pass, O(n). Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.

The problem, in real life

Raju (from episode 4) writes down his chai stall's profit every evening, in ₹100s. Loss days are negative:

3, 4, 7, 2, -3, 1, 4, 2

His cart's rent is ₹700. He asks: how many stretches of consecutive days earned exactly 7? Not the best stretch this time: every stretch that hits the exact target must be counted.

Problem statement

Given an integer array nums and an integer k, return the number of subarrays whose sum equals k. A subarray is a consecutive, non-empty part of the array. Constraints (LeetCode): 1 ≤ n ≤ 2 × 10⁴, -1000 ≤ nums[i] ≤ 1000, -10⁷ ≤ k ≤ 10⁷. In the video we push it to n = 10⁶.

nums k answer the subarrays
[3, 4, 7, 2, -3, 1, 4, 2] 7 4 [3, 4], [7], [7, 2, -3, 1], [1, 4, 2]
[1, 1, 1] 2 2 [1, 1] twice (positions 0-1 and 1-2)
[1, -1, 0] 0 3 [1, -1], [0], [1, -1, 0]
[0, 0, 0] 0 6 every one of the 6 subarrays
[5] 3 0 none

Brute force: every start, every end

import java.util.*;

public class Main {
    static int subarraySum(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;
    }
    public static void main(String[] args) {
        System.out.println(subarraySum(new int[]{3, 4, 7, 2, -3, 1, 4, 2}, 7));
    }
}

Output:

4

Don't stop at the first hit: a later negative number can bring the sum back to k, so keep extending.

On ten lakh (1,000,000) days:

int n = 1000000, nums[] = new int[n];
for (int i = 0; i < n; i++) nums[i] = (int) (i * 7919L % 201) - 100;
System.out.println(subarraySum(nums, 100));

Result: Time Limit Exceeded (the program is stopped after 8 seconds).

Why it is slow

An array of n elements has n(n+1)/2 subarrays, so checking each one is O(n²). For n = 10⁶ that is about 5 × 10¹¹ sums.

The tempting shortcut: a sliding window (and why it fails)

A sliding window keeps a stretch [left, right]: add the next number on the right, and while the sum is bigger than k, drop numbers from the left.

int count = 0, sum = 0, left = 0;
for (int right = 0; right < nums.length; right++) {
    sum += nums[right];
    while (sum > k && left <= right) sum -= nums[left++];
    if (sum == k) count++;
}
return count;
Input Window says Correct
[3, 4, 7, 2, -3, 1, 4, 2], k = 7 2 4
[1, 2, 3], k = 3 (all positive) 2 2

The window only works when every number is positive, because then adding a number always makes the sum bigger and dropping one always makes it smaller. With negative numbers, a sum that went above k can come back down, so the window can't know when to shrink. (We use the sliding window properly in episode 9, on a problem where it is safe.)

The key insight: Raju's running balance

Raju doesn't only write each day's profit; he writes the running balance, the total so far. That running total is a prefix sum:

P[j] = nums[0] + nums[1] + ... + nums[j]

The money earned from day i to day j is one subtraction:

sum(i..j) = P[j] - P[i-1]

So a stretch ending at j sums to k exactly when

P[i-1] = P[j] - k

At every j, we need how many earlier balances equal sum - k. That is a lookup, so keep every balance seen so far in a HashMap (balance → how many times it appeared), exactly like Two Sum in episode 2.

One subtle point: a stretch that starts at day 0 needs P[-1], the balance before any day, which is 0. So the map starts as {0: 1}.

Dry run: [3, 4, 7, 2, -3, 1, 4, 2], k = 7

j nums[j] sum (balance) need sum - 7 times seen count stretch found
start 0 0 map = {0: 1}
0 3 3 -4 0 0
1 4 7 0 1 1 [3, 4]
2 7 14 7 1 2 [7]
3 2 16 9 0 2
4 -3 13 6 0 2
5 1 14 7 1 3 [7, 2, -3, 1]
6 4 18 11 0 3
7 2 20 13 1 4 [1, 4, 2]

Answer: 4, in one pass.

The optimal solution: prefix sum + HashMap

import java.util.*;

public class Main {
    static int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> seen = new HashMap<>();
        seen.put(0, 1);
        int sum = 0, count = 0;
        for (int x : nums) {
            sum += x;
            count += seen.getOrDefault(sum - k, 0);
            seen.put(sum, seen.getOrDefault(sum, 0) + 1);
        }
        return count;
    }
    public static void main(String[] args) {
        System.out.println(subarraySum(new int[]{3, 4, 7, 2, -3, 1, 4, 2}, 7));
        System.out.println(subarraySum(new int[]{1, 1, 1}, 2));
        System.out.println(subarraySum(new int[]{1, -1, 0}, 0));
        System.out.println(subarraySum(new int[]{0, 0, 0}, 0));
        System.out.println(subarraySum(new int[]{5}, 3));
    }
}

Output:

4
2
3
6
0
  • [1, -1, 0], k = 0 → 3: [1, -1], [0] and [1, -1, 0].
  • [0, 0, 0], k = 0 → 6: all six subarrays sum to zero.

On ten lakh days (same input that timed out, k = 100):

long t = System.nanoTime();
int ans = subarraySum(nums, 100);
System.out.println(ans + "   " + (System.nanoTime() - t) / 1000000 + " ms");

Output (the time varies from run to run):

594034900   85 ms

The same solution in C++ and Python

#include <bits/stdc++.h>
using namespace std;

int subarraySum(const vector<int>& nums, int k) {
    unordered_map<int, int> seen;
    seen[0] = 1;
    int sum = 0, count = 0;
    for (int x : nums) {
        sum += x;
        auto it = seen.find(sum - k);
        if (it != seen.end()) count += it->second;
        seen[sum]++;
    }
    return count;
}

int main() {
    cout << subarraySum({3, 4, 7, 2, -3, 1, 4, 2}, 7) << "\n";   // 4
    cout << subarraySum({1, 1, 1}, 2) << "\n";                   // 2
    cout << subarraySum({0, 0, 0}, 0) << "\n";                   // 6
}
from collections import defaultdict

def subarray_sum(nums, k):
    seen = defaultdict(int)
    seen[0] = 1
    total = count = 0
    for x in nums:
        total += x
        count += seen[total - k]
        seen[total] += 1
    return count

print(subarray_sum([3, 4, 7, 2, -3, 1, 4, 2], 7))  # 4
print(subarray_sum([1, 1, 1], 2))                  # 2
print(subarray_sum([0, 0, 0], 0))                  # 6

In C++, seen[sum - k] would also work, but it inserts a zero entry for every missing key; find keeps the map small.

Complexity

Approach Time Extra space n = 10⁶
Every subarray with a running sum O(n²) O(1) Time Limit Exceeded
Sliding window O(n) O(1) fast but wrong with negatives
Prefix sum + HashMap O(n) average O(n) milliseconds

The map can hold up to n different balances, so we trade O(n) memory for O(n) time, exactly like Two Sum.

Common mistakes

Mistake What you see Why Fix
No seen.put(0, 1) 3 for Raju's days (answer is 4) stretches that start at day 0 need P[-1] = 0 put 0 → 1 in the map before the loop
Store sum before the lookup 3 for [1, 2, 3], k = 0 (answer is 0) with k = 0 the lookup finds today's own balance: an empty stretch look up first, then store
Sliding window 2 for Raju's days (answer is 4) negative numbers make sums shrink again prefix sums + map
seen.put(sum, 1) undercounts when a balance repeats each earlier day with that balance is a separate start store a count: getOrDefault(sum, 0) + 1
int count on huge inputs can overflow past 2,147,483,647 [0, 0, ..., 0], k = 0 has n(n+1)/2 answers use long if n can be large

Mini project: Raju's rent finder

Extend the program so it prints every stretch that earns exactly k, as day ranges. Store, for each balance, the list of days where it appeared (Map<Integer, List<Integer>>), and for each hit print day (i + 1) to day j for every stored i. Start the map with balance 0 at "day -1". For Raju's days the output should list days 0-1, 2-2, 2-5 and 5-7.

Practice

  1. Count subarrays of [4, 5, 0, -2, -3, 1] whose sum is divisible by 5 (LeetCode 974).
Solution

Two balances with the same remainder mod 5 enclose a stretch divisible by 5. Store ((sum % k) + k) % k (Java's % can be negative) and count repeats, starting with {0: 1}. Answer: 7.

  1. The length of the longest subarray of [1, -1, 5, -2, 3] with sum 3.
Solution

Store the first index where each balance appears (putIfAbsent), starting with {0: -1}. At j, if sum - k was seen at index i, the length is j - i. Answer: 4 ([1, -1, 5, -2]).

  1. The longest subarray of [0, 1, 0, 0, 1, 1, 0] with equal 0s and 1s (LeetCode 525).
Solution

Turn every 0 into -1; now you want the longest subarray with sum 0. Same code as practice 2 with k = 0. Answer: 6.

  1. Build a prefix array for [2, 4, 1, 3] and answer "sum of indexes 1 to 3".
Solution

P = [0, 2, 6, 7, 10] (with a leading 0, P[i] = sum of the first i numbers). Sum(1..3) = P[4] - P[1] = 10 - 2 = 8. Each query is O(1) after O(n) preparation.

Quick quiz

What does subarraySum(new int[]{1, 2, 1, 2, 1}, 3) return?

  • 2
  • 3
  • 4
  • 5
Answer

4. Balances: 1, 3, 4, 6, 7. Looking up balance - 3 finds 0, 1, 3 and 4 once each: [1, 2], [2, 1], [1, 2], [2, 1].

Interview questions

  1. Why can't you use a sliding window here? Numbers can be negative, so extending a window can make its sum smaller and shrinking can make it bigger; the window has no safe rule for when to move.
  2. What does the map store, and why a count? Prefix sum → how many times it has appeared; each occurrence is a different start position.
  3. Why initialize the map with {0: 1}? It represents the empty prefix before index 0, so subarrays starting at index 0 are counted.
  4. Why look up before you store? Otherwise, with k = 0, the current prefix matches itself and counts an empty subarray.
  5. Time and space? O(n) average time (hash lookups are O(1) on average), O(n) space.
  6. How would you return the longest such subarray instead? Store the first index of each prefix sum and maximize j - firstIndex[sum - k].

Glossary

Term Meaning
Subarray A consecutive, non-empty part of an array
Prefix sum The running total P[j] = nums[0] + ... + nums[j]
Range sum The sum of nums[i..j], equal to P[j] - P[i-1]
Empty prefix The sum before any element, 0; stored as {0: 1}
HashMap A key → value table with O(1) average lookup and insert
getOrDefault Java map method: the value for a key, or a default if the key is missing
Sliding window A stretch [left, right] that grows and shrinks as it moves; safe only when moving the ends changes the sum in one direction
Time Limit Exceeded (TLE) The judge stopped the program because it ran too long
Average O(1) Fast on average; a hash map can be slower in rare worst cases

Summary

  • Counting every subarray is O(n²); a sliding window is fast but wrong with negative numbers.
  • A prefix sum turns any stretch into one subtraction: sum(i..j) = P[j] - P[i-1].
  • Count the earlier prefix sums equal to sum - k with a HashMap, starting from {0: 1}, looking up before storing.
  • O(n) time, O(n) space. The same pattern solves divisible-by-k, longest-with-sum-k and equal-0s-and-1s.

Next episode: Two pointers: 3Sum.