Sliding Window — Binary Subarrays With Sum
↗ LeetCode: Binary Subarrays With Sum · Medium · pattern chapter →
Given a binary array nums and integer goal, return the number of non-empty contiguous subarrays with sum equal to goal.
Example 1 — nums = [1,0,1,0,1], goal = 2 → 4 (subarrays: [1,0,1], [1,0,1,0], [0,1,0,1], [1,0,1]) Example 2 — nums = [0,0,0,0,0], goal = 0 → 15 (every subarray sums to 0) Example 3 — nums = [1,1,1], goal = 3 → 1
Constraints — 1 ≤ n ≤ 3 · 10⁴; nums[i] ∈ {0, 1}; 0 ≤ goal ≤ n. Brute is O(n²) = 9·10⁸ ops at n=3·10⁴ (TLE past 5 s). Sliding-window atMost(goal) − atMost(goal−1) runs in O(n) = 3·10⁴ ops.
⏱️Interview timer00:00
Approach 1 — Every subarray
Intuition. For each [i, j], sum bits; increment on match.
int numSubarraysWithSumBrute(int[] nums, int goal) {
int n = nums.length, count = 0;
for (int i = 0; i < n; i++) {
int s = 0;
for (int j = i; j < n; j++) {
s += nums[j];
if (s == goal) count++;
else if (s > goal) break;
}
}
return count;
}2
3
4
5
6
7
8
9
10
11
12
Complexity — Time O(n²); Space O(1).
Approach 2 — Prefix-sum hash map (works with any integers)
Insight from brute. Precompute prefix sums. Subarray [i, j] has sum goal iff pref[j+1] - pref[i] = goal → count for each j, how many earlier prefixes equal pref[j+1] - goal. Same recipe as Subarray Sum Equals K.
int numSubarraysWithSumPS(int[] nums, int goal) {
Map<Integer, Integer> cnt = new HashMap<>();
cnt.put(0, 1);
int pref = 0, res = 0;
for (int x : nums) {
pref += x;
res += cnt.getOrDefault(pref - goal, 0);
cnt.merge(pref, 1, Integer::sum);
}
return res;
}2
3
4
5
6
7
8
9
10
11
Complexity — Time O(n); Space O(n).
Approach 3 — atMost(goal) − atMost(goal−1) sliding window
Insight from prefix-sum. With non-negative integers, sums are monotone in window size — a plain sliding-window computes atMost(goal) in O(n) and O(1) space. Subtract atMost(goal-1) to get "exactly goal".
int numSubarraysWithSum(int[] nums, int goal) {
return atMost(nums, goal) - atMost(nums, goal - 1);
}
int atMost(int[] nums, int goal) {
if (goal < 0) return 0;
int left = 0, sum = 0, res = 0;
for (int right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum > goal) sum -= nums[left++];
res += right - left + 1;
}
return res;
}2
3
4
5
6
7
8
9
10
11
12
13
Complexity — Time O(n); Space O(1).
Try it yourself
Complexity summary
| Approach | Time | Space | Interview grade |
|---|---|---|---|
| Every subarray | O(n²) | O(1) | baseline |
| Prefix-sum hash map | O(n) | O(n) | works even for negatives |
Two atMost windows | O(n) | O(1) | optimum for non-negatives |
When to use which
- Binary / non-negative array + exact sum →
atMostsliding trick. - Arbitrary integers (negatives allowed) → prefix-sum hash map — sliding window breaks.
- Longest / shortest subarray with sum X (not count) → different template — see Minimum Size Subarray Sum.
- Return subarrays themselves → prefix-sum + track indices, or DP; loses O(n).
Related problems
- Subarray Sum Equals K — arbitrary integers
- Subarrays with K Different Integers — same
atMosttrick - Count Number of Nice Subarrays — same trick with odd counts