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:
- Positive Integers: All numbers in
numsare . This is critical because it ensures that adding an element always increases the sum and removing one decreases it monotonically. - Output Requirement: Return minimal length or 0 if impossible.
- Scale: Array size up to , requiring better than quadratic time complexity ().
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 solution because we check roughly windows. Given nums.length can be up to , 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:
- The current length is valid; try shrinking it from the left to see if we can find a smaller valid subarray ending at
right. - Expanding
rightwill 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
- Initialize
leftpointer, a running sum variable (current_sum), and a result tracker for minimum length (min_len) set to infinity or -1. - Iterate with a
rightpointer from 0 to end of array:- Add
nums[right]tocurrent_sum.
- Add
- While the window is valid (i.e.,
current_sum >= target):- Update
min_lenif current window size (right - left + 1) is smaller than previous best. - Subtract
nums[left]from sum and incrementleftto shrink the window, attempting to find a shorter subarray that still meets the condition.
- Update
- After iterating through all elements:
- If no valid subarray was found (
min_lenremains infinity), return 0. - Otherwise, return
min_len.
- If no valid subarray was found (
Complexity Analysis
- Time: . The
rightpointer moves from start to end once ( steps). Theleftpointer also moves at most times total because it only increments and never resets. Each element is added and removed exactly once. - Space: 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_lenremains 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, updatingmin_lento 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 (, ) fit within standard integer types without overflow issues in most languages, though logic remains consistent regardless of specific bit-width.