Domain 2MediumCORE

Minimum Size Subarray Sum

We are given an array nums containing only positive integers and a target sum value. We need to find the smallest length (number of elements) of any contiguous subarray where the sum is at least equal to target. If no such subarray exists, we return 0.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Array#Two Pointers#Binary Search

209. Minimum Size Subarray Sum

Model: qwen3.5:9b
Topics: Array,Two Pointers,Binary Search
FAANG asked: 1
Acceptance rate: 39.8%


Problem Breakdown

We are given an array nums containing only positive integers and a target sum value. We need to find the smallest length (number of elements) of any contiguous subarray where the sum is at least equal to target. If no such subarray exists, we return 0.

Key constraints:

  1. Positive Integers: All numbers in nums are ≥1\ge 1. This is critical because it ensures that adding an element always increases the sum and removing one decreases it monotonically.
  2. Output Requirement: Return minimal length or 0 if impossible.
  3. Scale: Array size up to 10510^5, requiring better than quadratic time complexity (O(n)O(n)).

Intuition

A brute-force approach would iterate through every possible start index and end index, calculating the sum for each subarray. This results in an O(n2)O(n^2) solution because we check roughly n×(n+1)2\frac{n \times (n+1)}{2} windows. Given nums.length can be up to 10510^5, this will time out on most platforms.

The key insight comes from the fact that all numbers are positive. If a window [left, right] has a sum greater than or equal to target, we know two things:

  1. The current length is valid; try shrinking it from the left to see if we can find a smaller valid subarray ending at right.
  2. Expanding right will only increase the sum, so we don’t need to reset our window when moving forward—we just keep expanding until the condition fails or we hit the end of the array.

This monotonicity allows us to use the Sliding Window (Two Pointers) technique where both pointers move forward at most once through the array.

Approach

  1. Initialize left pointer, a running sum variable (current_sum), and a result tracker for minimum length (min_len) set to infinity or -1.
  2. Iterate with a right pointer from 0 to end of array:
    • Add nums[right] to current_sum.
  3. While the window is valid (i.e., current_sum >= target):
    • Update min_len if current window size (right - left + 1) is smaller than previous best.
    • Subtract nums[left] from sum and increment left to shrink the window, attempting to find a shorter subarray that still meets the condition.
  4. After iterating through all elements:
    • If no valid subarray was found (min_len remains infinity), return 0.
    • Otherwise, return min_len.

Complexity Analysis

  • Time: O(n)O(n). The right pointer moves from start to end once (nn steps). The left pointer also moves at most nn times total because it only increments and never resets. Each element is added and removed exactly once.
  • Space: O(1)O(1) extra space (excluding input storage), as we use a few integer variables for pointers and sums.

Solution

def minSubArrayLen(target: int, nums: list[int]) -> int:
    n = len(nums)
    left = 0
    current_sum = 0
    min_len = float('inf') # Initialize to infinity to track if we found a valid window

    for right in range(n):
        current_sum += nums[right]
        
        # While the sum is sufficient, try shrinking from the left
        while current_sum >= target:
            current_window_length = right - left + 1
            min_len = min(min_len, current_window_length)
            
            # Shrink window to find a smaller valid subarray ending at 'right' or earlier
            current_sum -= nums[left]
            left += 1
            
    return 0 if min_len == float('inf') else min_len

Edge Cases Handled

  • No Valid Subarray: If min_len remains infinity (e.g., sum of entire array < target), the function returns 0.
  • Single Element Match: The loop handles cases where a single element equals or exceeds target, updating min_len to 1 correctly before shrinking logic runs.
  • Exact Target Sum at End: If the last elements form exactly the target sum, the while loop executes once for that window size and updates min_len.
  • Large Values/Overflow: Python handles large integers automatically; constraints (target≤109target \le 10^9, nums[i]≤105nums[i] \le 10^5) fit within standard integer types without overflow issues in most languages, though logic remains consistent regardless of specific bit-width.