Smallest Subarray with Sum ≥ Target

Problem Overview

Given an array of positive integers and a target sum, find the length of the shortest contiguous subarray whose sum is at least the target. Return 0 if no such subarray exists.

Why solve this?

The introductory variable-size sliding window: unlike a fixed-k window, both edges move independently, expanding to search and shrinking to optimize — and the technique's correctness quietly depends on every value being positive.

Pattern Recognition

Whenever a window needs to grow until some condition is met and then shrink as far as possible while the condition still holds, that's a variable-size sliding window — but only when growing the window is guaranteed to only ever help the condition, which for a sum-based condition means every value must be positive.

Prerequisites

• Maximum Sum Subarray of Size K — the same window-sum bookkeeping, now with a window whose size isn't fixed in advance.

Hints

1. Grow the window from the right by adding elements until its sum reaches at least the target.
2. Once the sum qualifies, try shrinking from the left as far as possible while the sum still meets the target, recording the shortest length found.
3. This shrink-while-valid step is only safe because every element is positive: removing an element from the left is guaranteed to decrease the sum, never increase it, so shrinking never accidentally re-qualifies a window that had stopped qualifying.

Approach

This is a variable-size sliding window: unlike Maximum Sum Subarray of Size K's fixed width, the window here grows and shrinks based on a condition. Expand the window by moving a right pointer forward, adding each new element to a running window sum. Whenever that sum becomes at least the target, the current window is a valid candidate, so record its length and then shrink the window from the left — subtracting the leftmost element and advancing the left pointer — for as long as the sum still meets or exceeds the target, updating the best (smallest) length at each valid shrink. Once the sum drops below the target, resume expanding from the right. This shrink-while-valid step depends entirely on every element being positive: removing an element from the left is guaranteed to only decrease the window's sum, never increase it, which is what makes 'keep shrinking while still valid' a safe, monotonic operation. If the array contained negative numbers, shrinking the window could unpredictably raise the sum back above the target after it had dropped below, breaking the greedy shrink logic entirely. If the right pointer reaches the end of the array without the sum ever reaching the target, no qualifying subarray exists, and the answer is 0.

Code

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0, windowSum = 0;
        int best = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right++) {
            windowSum += nums[right];
            while (windowSum >= target) {
                best = Math.min(best, right - left + 1);
                windowSum -= nums[left];
                left++;
            }
        }
        return best == Integer.MAX_VALUE ? 0 : best;
    }
}

Related Problems

• Reverse an Arrayeasy
• Second Largest Element in an Arrayeasy
• Plus Oneeasy
• Running Sum of 1d Arrayeasy