Minimum Size Subarray Sum — Shortest Window Reaching Target

Problem Statement#

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray whose sum is at least target. If no such subarray exists, return 0.

Constraints:

• 1 <= target <= 10^9
• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^4

Input:  target = 7, nums = [2,3,1,2,4,3]
Output: 2

Input:  target = 4, nums = [1,4,4]
Output: 1

Why This Problem Matters#

LeetCode 209 is the canonical "minimum length subarray with sum at least K" problem. It is asked at Google, Amazon, Microsoft, Apple, and Bloomberg, often as a phone screen warmup before a harder follow-up.

The problem is a great teaching tool because the optimal O(n) sliding window only works when all values are positive. The constraint hides a powerful idea: positivity makes the prefix sum monotone, which guarantees that shrinking from the left never accidentally invalidates the window for future expansions.

A common follow-up is LC 862 (Shortest Subarray with Sum at Least K) where negatives are allowed. That version requires a monotonic deque — a fundamentally different technique. Knowing why the sliding window fails on negatives is itself a frequent interview question.

The Core Insight#

Maintain a window [l, r], expand right one step at a time and add nums[right] to the running sum. Whenever the running sum is at least target, shrink from the left as long as the sum stays at or above the target — recording the shorter window each time you can.

The greedy shrink is safe because all values are positive: removing the leftmost element strictly decreases the sum, so the moment shrinking would drop below the target you stop, and the answer for windows ending at right is captured.

If the loop ends without ever reaching the target, return 0.

Visual Dry Run#

Trace target = 7, nums = [2, 3, 1, 2, 4, 3].

Final answer: 2.

Solution (Optimal)#

class Solution:
    def minSubArrayLen(self, target: int, nums: list[int]) -> int:
        left = 0
        running = 0
        best = float('inf')
 
        for right, v in enumerate(nums):
            running += v
            while running >= target:
                best = min(best, right - left + 1)
                running -= nums[left]
                left += 1
 
        return 0 if best == float('inf') else best

var minSubArrayLen = function (target, nums) {
    let left = 0;
    let running = 0;
    let best = Infinity;
 
    for (let right = 0; right < nums.length; right++) {
        running += nums[right];
        while (running >= target) {
            best = Math.min(best, right - left + 1);
            running -= nums[left];
            left++;
        }
    }
 
    return best === Infinity ? 0 : best;
};

Time: O(n) — each index added and removed exactly once. Space: O(1) — a few scalars.

Common Mistakes#

• Using if instead of while for shrinking. You must shrink as far as possible while staying at or above target.
• Returning -1 or undefined when no subarray exists. The contract is to return 0.
• Forgetting that the constraint is >= target, not > target.
• Trying to apply the same template when negatives are allowed. It silently fails.
• Initializing best to 0 — the conditional return then misfires.

Interview Tips#

• Verbalize "all values positive, so shrinking is greedy-safe" up front.
• Lead with the sliding window solution, then mention the prefix-sum-plus-binary-search O(n log n) alternative for completeness.
• If the interviewer asks about negatives, name LC 862 and the deque-based O(n) approach.
• Use Infinity (or float('inf')) for the answer sentinel — cleaner than length+1.
• Walk through target = 4, nums = [1, 4, 4] to show the answer is 1.

Follow-up Questions#

• Negative values allowed. Hint: monotonic deque on prefix sums (LC 862).
• Sum exactly equal to target. Hint: HashMap of prefix sums.
• Return the actual subarray. Hint: track left and right when best updates.
• 2D version: smallest submatrix with sum at least target. Hint: extend with row prefix sums plus this template column-wise.
• Streaming nums. Hint: same algorithm; just keep left and running between feeds.

Key Takeaways#

• LeetCode 209 finds the minimum length subarray whose sum is at least target.
• The shrinkable sliding window is O(n) and works because values are positive.
• Use while (not if) to shrink — you may shrink several times after a single expansion.
• Return 0 when no valid window exists.
• For negatives, switch to monotonic deque on prefix sums (LC 862).
• Time O(n), space O(1).
• Frequently asked at Google, Amazon, Microsoft, Apple, and Bloomberg.