Find the minimum length of a contiguous subarray whose sum is at least a given target.

How to think about it

Recognise the pattern

The signal is “minimum length / shortest window” + contiguous subarray + positive integers + sum condition. The positive-integers constraint is crucial: it means adding elements always grows the sum, and removing them always shrinks it. That monotonicity is what lets a sliding window work — if you had negative numbers, removing an element from the left might accidentally increase the sum, breaking the shrink step.

Build the approach step by step

Brute force tries every (i, j) pair, computes the subarray sum, checks against target. O(n²).

The sliding window approach:

1. Use left=0, right=0, running window_sum=0, and best=infinity.
2. Expand: add nums[right] to window_sum, advance right.
3. Shrink: while window_sum >= target, record right - left as a candidate answer, then subtract nums[left] and advance left.
4. Repeat until right reaches the end.

Why does this work? Every time the window is valid (sum >= target), we greedily shrink from the left to find the shortest valid window ending at the current right. Because all values are positive, shrinking can only decrease the sum, so we stop shrinking the moment the constraint breaks.

Walk through [2, 3, 1, 2, 4, 3], target=7:

• right grows until sum=7 (window [2,3,1,2,4] len=5? no, let’s trace):
  • sum = 2,3,4,6,10 at right=4: 10 >= 7, record len=5, shrink left: sum = 8, record len=4, sum = 5 < 7 stop
  • right=5: sum = 8, record len=3, shrink: sum = 7, record len=2, shrink: sum = 3 < 7 stop
• Best = 2 ✓

Complexity

• Time — O(n): right advances n times; left advances at most n times total across all iterations of the inner while. Each element enters and exits the window exactly once.
• Space — O(1): a handful of variables.

The trap and an important variant