Sliding Window — Minimum Size Subarray Sum
↗ LeetCode: Minimum Size Subarray Sum · Medium · pattern chapter →
Given a positive-int array nums and target target, return the minimal length of a contiguous subarray whose sum is at least target. Return 0 if none.
Example 1 — target = 7, nums = [2,3,1,2,4,3] → 2 (the subarray [4,3] sums to 7) Example 2 — target = 4, nums = [1,4,4] → 1 (single 4) Example 3 — target = 11, nums = [1,1,1,1,1,1,1,1] → 0 (impossible)
Constraints — 1 ≤ n ≤ 10⁵; 1 ≤ nums[i], target ≤ 10⁴. All values positive.. Brute enumerates all subarrays in O(n²) = 10¹⁰ ops (TLE past n=10⁴). Sliding window is O(n) = 10⁵ ops = <5 ms.
⏱️Interview timer00:00
Approach 1 — All subarrays
Intuition. For each i, expand j and accumulate the sum. On first sum ≥ target, record length and break the inner loop (extending further only lengthens).
int minSubArrayLenBrute(int target, int[] nums) {
int best = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; i++) {
int sum = 0;
for (int j = i; j < nums.length; j++) {
sum += nums[j];
if (sum >= target) { best = Math.min(best, j - i + 1); break; }
}
}
return best == Integer.MAX_VALUE ? 0 : best;
}2
3
4
5
6
7
8
9
10
11
Complexity — Time O(n²) worst; Space O(1).
Approach 2 — Sliding window (positives only)
Insight from brute. With positive values, growing right monotonically increases sum, and shrinking left monotonically decreases it. So we can extend right until sum ≥ target, then shrink left while the window is still valid — tracking the min length.
int minSubArrayLen(int target, int[] nums) {
int left = 0, sum = 0, best = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum >= target) {
best = Math.min(best, right - left + 1);
sum -= nums[left++];
}
}
return best == Integer.MAX_VALUE ? 0 : best;
}2
3
4
5
6
7
8
9
10
11
Complexity — Time O(n) — each index enters and leaves the window at most once; Space O(1).
Approach 3 — Prefix sum + binary search (extends to negatives? No)
Insight from sliding. Sliding window fails once values can be negative — shrinking doesn't monotonically decrease sum. A prefix-sum + binary-search approach handles positives at O(n log n) and generalizes to a monotonic deque approach for negatives (see Shortest Subarray with Sum at Least K).
int minSubArrayLenBS(int target, int[] nums) {
int n = nums.length;
int[] pref = new int[n + 1];
for (int i = 0; i < n; i++) pref[i + 1] = pref[i] + nums[i];
int best = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
int need = pref[i] + target;
int j = Arrays.binarySearch(pref, i + 1, n + 1, need);
if (j < 0) j = -j - 1;
if (j <= n) best = Math.min(best, j - i);
}
return best == Integer.MAX_VALUE ? 0 : best;
}2
3
4
5
6
7
8
9
10
11
12
13
Complexity — Time O(n log n); Space O(n). Loses to sliding for positives-only but sets up the generalization.
Try it yourself
Complexity summary
| Approach | Time | Space | Interview grade |
|---|---|---|---|
| All subarrays | O(n²) | O(1) | baseline |
| Sliding window | O(n) | O(1) | expected optimum for positives |
| Prefix + binary search | O(n log n) | O(n) | polish — generalizes to negatives via deque |
When to use which
- First pass — sliding window is the right answer for positives.
- "What if values can be negative?" → mention the generalization: monotonic deque on prefix sums.
- "Return the subarray itself" → track
(bestL, bestLen)and slice. - "Sum exactly equal to target" → different problem — needs prefix-sum + hash-map (see Subarray Sum Equals K).
Related problems
- Shortest Subarray with Sum at Least K — with negatives, monotonic deque
- Subarray Sum Equals K — count of subarrays, not length
- Maximum Subarray — Kadane
- Minimum Window Substring — same shrinking template