Minimum Size Subarray Sum

MediumSliding Window · Prefix Sum🧩 Sliding Window LeetCode #209 ↗Updated Oct 30, 2026

Problem

You get an array nums of positive integers and a positive target. Find the length of the shortest contiguous subarray whose sum is at least target. If no subarray reaches the target, return 0.

Inputtarget = 7, nums = [2,3,1,2,4,3]Output2 (subarray [4,3])

Inputtarget = 4, nums = [1,4,4]Output1

Inputtarget = 11, nums = [1,1,1,1,1]Output0

1 ≤ n ≤ 10⁵ · 1 ≤ nums[i] ≤ 10⁴ · 1 ≤ target ≤ 10⁹ · Follow-up: after O(n), try an O(n log n) solution.

Try it yourself

Java

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

All values are positive, so growing a window only raises its sum and shrinking only lowers it. That monotonicity lets two pointers sweep once: extend the right edge until the sum is big enough, then squeeze the left edge as far as possible.

PatternSliding Window

Instinct Longest, shortest or count of contiguous subarrays/substrings meeting a rule? Grow a window on the right, shrink it on the left, never step back.

Memory hack Move like a caterpillar - the head stretches forward to grab, the tail pulls up only when the body breaks the rule.

Open the Sliding Window guide →

Approaches

Brute ForceEvery Start, Running Sum

Time O(n²)Space O(1)

Fix each start index and extend the end one step at a time while keeping a running sum. The first end where the sum reaches target gives the shortest window for that start, so we can stop extending immediately.

Java

public int minSubArrayLen(int target, int[] nums) {
    int n = nums.length;
    int best = Integer.MAX_VALUE;
    for (int start = 0; start < n; start++) {
        int sum = 0;
        for (int end = start; end < n; end++) {
            sum += nums[end];
            if (sum >= target) {
                best = Math.min(best, end - start + 1);
                break; // longer windows from this start can't be shorter
            }
        }
    }
    return best == Integer.MAX_VALUE ? 0 : best;
}

Correct and simple, but quadratic — too slow for n = 10⁵.

BetterPrefix Sums + Binary Search

Time O(n log n)Space O(n)

Build prefix[i] = sum of the first i values. Since values are positive, prefix is strictly increasing, so for each start i we can binary-search the smallest j with prefix[j] ≥ prefix[i] + target; the window length is j - i.

Java

public int minSubArrayLen(int target, int[] nums) {
    int n = nums.length;
    long[] prefix = new long[n + 1];
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    int best = Integer.MAX_VALUE;
    for (int i = 0; i < n; i++) {
        long need = prefix[i] + target;
        // first index j in [i+1, n] with prefix[j] >= need
        int lo = i + 1, hi = n + 1;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (prefix[mid] >= need) hi = mid;
            else lo = mid + 1;
        }
        if (lo <= n) best = Math.min(best, lo - i);
    }
    return best == Integer.MAX_VALUE ? 0 : best;
}

Answers the follow-up and is fast, but needs O(n) memory and a log factor.

OptimalVariable-Size Sliding Window

Time O(n)Space O(1)

Move right forward adding each value. Whenever the window sum reaches target, record its length and drop nums[left], repeating while the sum still qualifies. Each index enters and leaves the window at most once, so the total work is linear.

Java

public int minSubArrayLen(int target, int[] nums) {
    int left = 0, sum = 0;
    int best = Integer.MAX_VALUE;
    for (int right = 0; right < nums.length; right++) {
        sum += nums[right];
        // shrink while the window is still large enough
        while (sum >= target) {
            best = Math.min(best, right - left + 1);
            sum -= nums[left];
            left++;
        }
    }
    return best == Integer.MAX_VALUE ? 0 : best;
}

Dry runtarget = 7, nums = [2,3,1,2,4,3]

l leftr right changed

r=2
2
l
3

1
r
2

4

3

sum=6 < 7
r=3
2
l
3

1

2
r
4

3

sum=8, best=4
shrink
2

3
l
1

2
r
4

3

sum=6, l=1
r=4
2

3

1

2
l
4
r
3

shrunk: best=3
r=5
2

3

1

2

4
l
3
r
sum=7, best=2
end
2

3

1

2

4

3
l r
answer 2 ✔

Single pass with constant memory — the expected interview answer.

Pro tip

Mention why it fails with negatives: shrinking might raise the sum, so the window logic breaks (use a monotonic deque on prefix sums instead, LC 862).

At a glance

Level	Approach	Time	Space
Brute Force	Every Start, Running Sum	`O(n²)`	`O(1)`
Better	Prefix Sums + Binary Search	`O(n log n)`	`O(n)`
Optimal	Variable-Size Sliding Window	`O(n)`	`O(1)`

Common pitfalls

Using if instead of while to shrink — misses shorter windows.
Returning Integer.MAX_VALUE when nothing qualifies instead of 0.
Applying the window to arrays with negatives — the monotonic argument no longer holds.

Interview tips

Point out the positivity constraint early; it is what makes two pointers valid.
Argue O(n) by counting moves: each pointer advances at most n times.
Offer the prefix-sum + binary-search version when asked for O(n log n).

Pattern

Variable sliding window → shortest/longest contiguous range with a monotone condition over non-negative values.

My notes saved in this browser