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
- 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.
- 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]).
- 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.
- 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
- 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.
- What does the map store, and why a count? Prefix sum → how many times it has appeared; each occurrence is a different start position.
- Why initialize the map with {0: 1}? It represents the empty prefix before index 0, so subarrays starting at index 0 are counted.
- Why look up before you store? Otherwise, with k = 0, the current prefix matches itself and counts an empty subarray.
- Time and space? O(n) average time (hash lookups are O(1) on average), O(n) space.
- 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 - kwith 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.