Minimum Size Subarray Sum [Medium] — Sliding Window, Brute Force, and Binary Search [Amazon / Microsoft]

Problem Statement#

Given a positive integer target and an array of positive integers nums, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

A subarray is a contiguous non-empty sequence of elements within the array.

Example 1:

Input:  target = 7,  nums = [2, 3, 1, 2, 4, 3]
Output: 2
Explanation: [4, 3] has sum 7 >= 7, and length 2 is the shortest such subarray.

Example 2:

Input:  target = 4,  nums = [1, 4, 4]
Output: 1
Explanation: [4] alone satisfies sum >= 4, and a subarray of length 1 is optimal.

Example 3:

Input:  target = 11,  nums = [1, 1, 1, 1, 1, 1, 1, 1]
Output: 0
Explanation: Even the full array sums to 8, which is less than 11. No valid subarray exists.

Constraints:

• 1 <= target <= 10^9
• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^4
• Follow-up: Can you solve it in O(n log n) time if the O(n) solution is trivial to you?

Why This Problem Matters#

LeetCode 209 is a foundational problem that shows up consistently in Amazon and Microsoft phone screens. It is tagged as Medium, but what makes it interview-gold is not the difficulty of the code — it is the progression of ideas the problem forces you to articulate.

When an interviewer at Amazon presents this problem, they are watching for a specific arc: start with the naive O(n²) brute force, recognize why it wastes work, explain the sliding window insight that eliminates the redundancy, implement it cleanly, and then — when asked "can you do better than O(n)?" — pivot to the O(n log n) binary search approach using prefix sums. Candidates who only know the sliding window answer and cannot explain the binary search variant leave roughly half the interview value on the table.

Beyond the interview, the problem pattern underlies real engineering tasks: streaming budget monitors that alert when a rolling window of spending exceeds a threshold, packet-burst detection in network monitoring systems, and rate-limiting windows in API gateways. Any time you need "the shortest contiguous chunk that crosses a threshold," this is the algorithm you reach for.

The problem is also a perfect vehicle for understanding the difference between a fixed-size sliding window (where the window size is given and you slide it across) and a variable-size sliding window (where the window expands and contracts based on a condition). LC 209 is the canonical variable-size example.

The Sliding Window Insight (variable-size window)#

The brute force approach tries every possible subarray: for each left boundary i, walk right boundary j from i to n-1, computing the running sum, stopping when the sum first reaches target. This is O(n²) and it wastes enormous amounts of work — every time you advance i by one, you recompute sums you already know.

The insight that breaks the O(n²) barrier comes from a single observation:

All values in nums are positive.

Because all values are positive, adding any element to the window can only increase the sum. This gives us two monotone properties:

1. If a window [left, right] satisfies sum >= target, then any larger window containing it also satisfies the condition — we can safely shrink from the left.
2. If a window [left, right] has sum < target, then expanding to the right can only increase the sum — we should add more elements.

These two properties are all you need for a two-pointer shrinkable sliding window:

• Expand: advance right one step, adding nums[right] to the running sum.
• Shrink: while sum >= target, record the current window length (it is a candidate answer), then advance left one step, subtracting nums[left] from the sum.

The shrinking step is the key insight: once the window sum exceeds target, we do not need to blindly check all smaller windows from scratch. We know the sum is too large, so we move the left boundary inward — the sum decreases, and we stop when it drops below target again.

Why is this O(n)? Each element enters the window exactly once (when right passes over it) and leaves the window exactly once (when left passes over it). The total number of pointer movements across the entire run is therefore at most 2n, giving us O(n) time with O(1) space.

The positivity constraint is not a detail — it is the entire reason the algorithm works. If nums could contain negative numbers, shrinking the window from the left could decrease the sum below target even when the window is still large, breaking the monotonicity guarantee. The O(n log n) binary search approach handles the negative-number variant; more on that in the Solutions section.

Visual Dry Run (step-by-step trace)#

Let us trace through Example 1: target = 7, nums = [2, 3, 1, 2, 4, 3].

We maintain: left = 0, current_sum = 0, min_length = infinity.

Index:   0   1   2   3   4   5
Value:   2   3   1   2   4   3
 
─────────────────────────────────────────────────────────────
Step 1: right = 0
  Add nums[0] = 2  →  sum = 2
  sum (2) < target (7), do NOT shrink
  Window: [2]  sum=2
 
─────────────────────────────────────────────────────────────
Step 2: right = 1
  Add nums[1] = 3  →  sum = 5
  sum (5) < target (7), do NOT shrink
  Window: [2,3]  sum=5
 
─────────────────────────────────────────────────────────────
Step 3: right = 2
  Add nums[2] = 1  →  sum = 6
  sum (6) < target (7), do NOT shrink
  Window: [2,3,1]  sum=6
 
─────────────────────────────────────────────────────────────
Step 4: right = 3
  Add nums[3] = 2  →  sum = 8
  sum (8) >= target (7):
    Window length = right - left + 1 = 3 - 0 + 1 = 4
    min_length = min(inf, 4) = 4
    Remove nums[left=0] = 2  →  sum = 6,  left = 1
  sum (6) < target, stop shrinking
  Window: [3,1,2]  sum=6
 
─────────────────────────────────────────────────────────────
Step 5: right = 4
  Add nums[4] = 4  →  sum = 10
  sum (10) >= target (7):
    Window length = 4 - 1 + 1 = 4
    min_length = min(4, 4) = 4
    Remove nums[left=1] = 3  →  sum = 7,  left = 2
  sum (7) >= target (7):
    Window length = 4 - 2 + 1 = 3
    min_length = min(4, 3) = 3
    Remove nums[left=2] = 1  →  sum = 6,  left = 3
  sum (6) < target, stop shrinking
  Window: [2,4]  sum=6
 
─────────────────────────────────────────────────────────────
Step 6: right = 5
  Add nums[5] = 3  →  sum = 9
  sum (9) >= target (7):
    Window length = 5 - 3 + 1 = 3
    min_length = min(3, 3) = 3
    Remove nums[left=3] = 2  →  sum = 7,  left = 4
  sum (7) >= target (7):
    Window length = 5 - 4 + 1 = 2
    min_length = min(3, 2) = 2     ← NEW BEST
    Remove nums[left=4] = 4  →  sum = 3,  left = 5
  sum (3) < target, stop shrinking
  Window: [3]  sum=3
 
─────────────────────────────────────────────────────────────
right = 6: out of bounds, loop ends.
 
Answer: min_length = 2  ✓  (the subarray [4, 3])

Notice that in Step 5, the inner while loop executed twice — the window shrank twice in one outer iteration. That is what "variable-size" means: the window can shrink by any amount in a single step. And yet across all six outer steps, left moved a total of five times and right moved six times — twelve pointer movements total for six elements, firmly O(n).

Common Mistakes#

Mistake 1: Updating min_length After the shrink loop instead of Inside It#

The most common implementation error is recording the window length after the while loop exits rather than inside it. Consider this incorrect pattern:

# WRONG — records the window AFTER over-shrinking
while current_sum >= target:
    current_sum -= nums[left]
    left += 1
min_length = min(min_length, right - left + 1)   # left has already moved past the optimal position

By the time the while loop exits, left has been advanced one step too far — to the position where sum < target. The length recorded at that point is one larger than the optimal window. The fix is to record the length before removing nums[left]:

# CORRECT — record while the window is still valid
while current_sum >= target:
    min_length = min(min_length, right - left + 1)   # record FIRST
    current_sum -= nums[left]
    left += 1

Mistake 2: Initializing min_length to 0 Instead of Infinity#

If min_length starts at 0, the min() call will always return 0 because no window length can be negative. The answer 0 is reserved for the case where no valid subarray exists at all, so you would confuse "no solution" with "wrong minimum."

Always initialize min_length = float('inf') (Python) or Infinity (JavaScript) and convert to 0 at the very end only if min_length was never updated.

Mistake 3: Using This Algorithm When nums Can Contain Negative Numbers or Zeros#

The sliding window approach requires that all elements are positive so that the window sum is strictly monotone as the window grows. If nums[i] can be 0 or negative, adding an element to the right no longer guarantees the sum increases, and shrinking from the left no longer guarantees the sum decreases. The monotonicity breaks, and the algorithm produces wrong answers.

The constraints for LC 209 explicitly state nums[i] >= 1, so this is safe. But in a real interview, always verify this assumption. If the interviewer modifies the problem to allow non-positive values, you must switch to the prefix-sum + binary search approach (see the O(n log n) solution below).

Mistake 4: Off-by-One in the Binary Search Approach#

In the O(n log n) approach, you build a prefix sum array of length n + 1 where prefix[0] = 0 and prefix[i] = nums[0] + ... + nums[i-1]. For each starting index i, you want the smallest j such that prefix[j] - prefix[i] >= target, which means prefix[j] >= prefix[i] + target. You binary-search for prefix[i] + target in prefix[i+1..n].

The off-by-one trap: the prefix array is 1-indexed (it has n + 1 elements). The window length is j - i, not j - i + 1, because prefix[j] represents the sum of nums[0..j-1]. Getting this wrong produces window lengths that are off by one across the board.

Solutions#

Python#

import math
import bisect
from typing import List
 
 
class Solution:
 
    # ─────────────────────────────────────────────────
    # Approach 1: Brute Force — O(n²) time, O(1) space
    # ─────────────────────────────────────────────────
    def minSubArrayLen_brute(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        min_length = float('inf')    # sentinel: no valid window found yet
 
        for left in range(n):        # try every possible left boundary
            current_sum = 0
 
            for right in range(left, n):   # expand right boundary one step at a time
                current_sum += nums[right]
 
                if current_sum >= target:
                    # This is the shortest window starting at 'left' that meets the target
                    window_len = right - left + 1
                    min_length = min(min_length, window_len)
                    break   # no need to expand further from this left — only gets longer
 
        # If min_length was never updated, no valid subarray exists
        return 0 if min_length == float('inf') else min_length
 
 
    # ──────────────────────────────────────────────────────────────
    # Approach 2: Sliding Window (Shrinkable) — O(n) time, O(1) space
    # ──────────────────────────────────────────────────────────────
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        left = 0               # left boundary of the sliding window
        current_sum = 0        # running sum of elements inside the window
        min_length = float('inf')   # best answer found so far (infinity = not found)
 
        for right in range(n):
            # Expand: include nums[right] in the current window
            current_sum += nums[right]
 
            # Shrink: as long as the window sum meets the target,
            # try to make the window smaller by moving left forward
            while current_sum >= target:
                # Record the window length BEFORE shrinking — this is the valid window
                window_len = right - left + 1
                min_length = min(min_length, window_len)
 
                # Remove the leftmost element and advance the left pointer
                current_sum -= nums[left]
                left += 1
 
        # If min_length is still infinity, no subarray reached the target
        return 0 if min_length == float('inf') else min_length
 
 
    # ─────────────────────────────────────────────────────────────────────────
    # Approach 3: Prefix Sum + Binary Search — O(n log n) time, O(n) space
    # Use this when the interviewer asks for the follow-up, or when nums can
    # contain negative numbers (though LC 209 only has positives, the binary
    # search approach generalises to monotone prefix sums i.e. positive arrays).
    # ─────────────────────────────────────────────────────────────────────────
    def minSubArrayLen_binary_search(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        min_length = float('inf')
 
        # Build prefix sum array: prefix[i] = sum of nums[0..i-1]
        # prefix has length n+1; prefix[0] = 0 (empty prefix)
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]
 
        # For each starting index i (0-indexed in nums),
        # we want the smallest j > i such that prefix[j] - prefix[i] >= target,
        # which means prefix[j] >= prefix[i] + target.
        # Binary-search for this threshold in the sorted prefix array.
        # (prefix is strictly increasing because all nums[i] > 0)
        for i in range(n):
            # The target prefix value we need to reach
            threshold = prefix[i] + target
 
            # bisect_left returns the index of the first prefix value >= threshold
            j = bisect.bisect_left(prefix, threshold)
 
            if j <= n:   # j == n+1 means no element reached the threshold
                # Window spans from index i to index j-1 in nums (0-indexed)
                # Length = j - i  (because prefix[j] covers nums[0..j-1])
                window_len = j - i
                min_length = min(min_length, window_len)
 
        return 0 if min_length == float('inf') else min_length

JavaScript#

/**
 * LeetCode 209 — Minimum Size Subarray Sum
 *
 * Three approaches:
 *   1. Brute Force        — O(n²) time, O(1) space
 *   2. Sliding Window     — O(n)  time, O(1) space  ← optimal for positives
 *   3. Prefix Sum + BSearch — O(n log n) time, O(n) space  ← follow-up
 */
 
 
// ─────────────────────────────────────────────────
// Approach 1: Brute Force — O(n²) time, O(1) space
// ─────────────────────────────────────────────────
 
/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
function minSubArrayLen_brute(target, nums) {
    const n = nums.length;
    let minLength = Infinity;   // sentinel: no valid window found yet
 
    for (let left = 0; left < n; left++) {   // try every left boundary
        let currentSum = 0;
 
        for (let right = left; right < n; right++) {   // expand right one step at a time
            currentSum += nums[right];
 
            if (currentSum >= target) {
                // Shortest window starting at 'left' that satisfies the condition
                const windowLen = right - left + 1;
                minLength = Math.min(minLength, windowLen);
                break;   // expanding further only makes the window longer
            }
        }
    }
 
    // If minLength was never updated, no valid subarray exists
    return minLength === Infinity ? 0 : minLength;
}
 
 
// ──────────────────────────────────────────────────────────────
// Approach 2: Sliding Window (Shrinkable) — O(n) time, O(1) space
// ──────────────────────────────────────────────────────────────
 
/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
function minSubArrayLen(target, nums) {
    const n = nums.length;
    let left = 0;          // left boundary of the sliding window
    let currentSum = 0;    // running sum of elements in the current window
    let minLength = Infinity;   // best answer found so far
 
    for (let right = 0; right < n; right++) {
        // Expand: add the element at right into the window
        currentSum += nums[right];
 
        // Shrink: while the window sum meets or exceeds the target,
        // the current window is valid — record it and try shrinking
        while (currentSum >= target) {
            // Record BEFORE shrinking: this is the smallest window ending at 'right'
            const windowLen = right - left + 1;
            minLength = Math.min(minLength, windowLen);
 
            // Remove the leftmost element and move the left boundary forward
            currentSum -= nums[left];
            left++;
        }
    }
 
    // Return 0 if we never found a valid subarray
    return minLength === Infinity ? 0 : minLength;
}
 
 
// ─────────────────────────────────────────────────────────────────────────
// Approach 3: Prefix Sum + Binary Search — O(n log n) time, O(n) space
// Useful as a follow-up when the interviewer asks for an O(n log n) solution,
// or conceptually when you need to handle arrays with non-positive elements
// (requires monotone prefix sums, so all-positive arrays work here).
// ─────────────────────────────────────────────────────────────────────────
 
/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
function minSubArrayLen_binarySearch(target, nums) {
    const n = nums.length;
    let minLength = Infinity;
 
    // Build prefix sum array of length n+1
    // prefix[i] = sum of nums[0..i-1];  prefix[0] = 0
    const prefix = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
 
    // For each starting index i, binary-search for the smallest j
    // such that prefix[j] >= prefix[i] + target
    for (let i = 0; i < n; i++) {
        const threshold = prefix[i] + target;
 
        // Binary search: find the leftmost index in prefix where value >= threshold
        let lo = i + 1;       // window must contain at least nums[i]
        let hi = n;           // rightmost valid index in prefix
        let j = n + 1;        // default: not found
 
        while (lo <= hi) {
            const mid = (lo + hi) >>> 1;   // unsigned right-shift avoids overflow
 
            if (prefix[mid] >= threshold) {
                j = mid;        // mid is a candidate — try to go smaller
                hi = mid - 1;
            } else {
                lo = mid + 1;   // mid is too small — search right
            }
        }
 
        if (j <= n) {
            // Window in nums spans indices [i, j-1], length = j - i
            const windowLen = j - i;
            minLength = Math.min(minLength, windowLen);
        }
    }
 
    return minLength === Infinity ? 0 : minLength;
}

Complexity Analysis#

Why O(n) for sliding window? Each element is added to the window once (when right visits it) and removed from the window at most once (when left passes it). The total work is at most 2n pointer movements regardless of how many times the inner while loop fires. This amortised argument is what makes the O(n) claim non-obvious at first glance — the inner loop looks like it could add a factor of n, but because each element is only ever removed once, the total cost is bounded.

Why O(n log n) for binary search? Building the prefix array is O(n). The outer loop runs n times, and each iteration performs a binary search over an array of at most n + 1 elements: O(log n) per iteration. Total: O(n) + O(n log n) = O(n log n).

Space comparison: The sliding window uses two integer variables — no extra memory regardless of input size. The binary search approach allocates the prefix array at O(n) extra space. In a memory-constrained environment (embedded systems, tight caches), the sliding window wins decisively.

Follow-up Questions (real FAANG follow-ups)#

"Can you solve this in O(n log n)?"#

This is the explicit follow-up printed in the LeetCode problem description. The answer is the prefix sum + binary search approach described above. Articulate the construction clearly: a prefix sum array converts the "subarray sum" question into a "difference of two prefix values" question, and binary search finds the optimal right boundary in O(log n) per left boundary.

"What if nums can contain negative numbers or zeros?"#

The sliding window breaks because the monotonicity guarantee is gone — adding a negative number shrinks the sum, so you cannot be sure that expanding right always gets you closer to the target. The prefix sum array is no longer strictly increasing.

The correct general approach for arbitrary integers is more complex: it requires a monotone deque on the prefix sum array to find the optimal window in O(n) time, or accepting the O(n log n) approach with a balanced BST (like a sorted structure that supports order-statistic queries). In practice, this variant is a Hard-level problem (similar in spirit to LC 862 — Shortest Subarray with Sum at Least K).

"What if the array is very large and lives on disk?"#

Stream the array in chunks. The sliding window algorithm is inherently streamable: you only need the current element at right, the element at left, and the two pointer positions. Unlike prefix sum (which requires the full array to be built first), the sliding window can process the input in a single sequential pass with O(1) memory — ideal for disk-based or network-streamed inputs.

"What if you need to find ALL subarrays of minimum length, not just the count?"#

Modify the algorithm to collect the starting index whenever min_length is updated to a strictly better value, and to collect all starting indices whenever it equals the current best. Track both best_length and a list of best_left positions. The time complexity stays O(n); the space grows to O(k) where k is the number of minimal-length subarrays.

"What if target is 0?"#

Every non-empty subarray of a positive integer array has sum >= 0 >= target = 0. The shortest non-empty subarray has length 1. Your code should return 1 immediately (or after one pass). Walk through whether your sliding window handles this: after adding nums[right] (which is positive), current_sum >= 0 = target is always true, so the window immediately shrinks to size 1. It works correctly.

This Pattern Solves#

The unifying principle: a variable-size shrinkable sliding window is the right tool whenever all of these hold:

1. The array contains only positive (or non-negative) values.
2. The condition on the window is monotone — satisfying the condition on a window guarantees any superset (larger window) also satisfies it.
3. You want the shortest window that satisfies the condition.

When condition 1 fails (negative values appear), replace the sliding window with a monotone deque on the prefix sum array.

Key Takeaways#

• LeetCode 209 — Minimum Size Subarray Sum is a Medium asked at Amazon and Microsoft; the variable-size shrinkable sliding window achieves O(n) time, O(1) space.
• Sliding window prerequisite: all elements must be positive — positivity creates the monotone property (expand increases sum, shrink decreases sum) that makes two pointers valid.
• The while loop inside the for loop still runs O(n) total — each element enters and leaves the window at most once (amortized analysis).
• Binary search fallback: build prefix sums, then binary search for the minimum subarray length — O(n log n) time, O(n) space; use when elements may be non-positive.
• Always ask "are all elements positive?" before proposing sliding window — negative numbers break the monotone property.
• Answer is float('inf') if no valid subarray exists — always return 0 in that case per the problem spec.
• The shrinkable sliding window template (expand right, shrink left while valid) also solves LC 76 (Minimum Window Substring) and LC 862 (Shortest Subarray with Sum at Least K).