Minimum Size Subarray Sum
Asked at Meta
Problem
Given an array of positive integers and a positive integer target, find the minimal length of a subarray whose sum is greater than or equal to target. If no such subarray exists, return 0.
Asked At
| Company | Difficulty | |
|---|---|---|
| Meta | MEDIUM | View all Meta questions → |
How to Think About It
Brute force: check every subarray with two nested loops — O(n^2).
Prefix sum + binary search: for each start index, binary search for the smallest end where prefix[end] - prefix[start] >= target.
Sliding window: expand right to accumulate sum, shrink left to find minimum length.
The sliding window approach is optimal at O(n) since all values are positive.
Maintain a running sum and update the answer each time the window sum meets or exceeds the target.
Optimal Approach
Use a sliding window. Expand the right pointer to accumulate the sum. Whenever the sum >= target, record the length and shrink the left pointer to try to minimize. Continue until the right pointer reaches the end. Return the minimum length found, or 0 if none was found. This runs in O(n) time with O(1) space since all values are positive.
What Trips People Up in Real Interviews
Clarify that all numbers are positive — this is critical for the sliding window to work.
Edge case: return 0 if no valid subarray exists (total sum < target).
Edge case: single element equal to or greater than target returns length 1.
Mention the O(n log n) prefix sum + binary search approach as an alternative.
Trace through [2,3,1,2,4,3] with target=7 to show the sliding window shrinking.
Solution Code
def minSubArrayLen(target: int, nums: list[int]) -> int:
left = 0
total = 0
min_len = float('inf')
for right in range(len(nums)):
total += nums[right]
while total >= target:
min_len = min(min_len, right - left + 1)
total -= nums[left]
left += 1
return 0 if min_len == float('inf') else min_lenFrequently Asked Questions
What is the Minimum Size Subarray Sum problem?
Given an array of positive integers and a positive integer target, find the minimal length of a subarray whose sum is greater than or equal to target. If no such subarray exists, return 0.
How do you solve Minimum Size Subarray Sum?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Minimum Size Subarray Sum?
Minimum Size Subarray Sum is asked at Meta. It is a medium difficulty problem.
What are common mistakes on Minimum Size Subarray Sum?
- Clarify that all numbers are positive — this is critical for the sliding window to work.
- Edge case: return 0 if no valid subarray exists (total sum < target).
- Edge case: single element equal to or greater than target returns length 1.
- Mention the O(n log n) prefix sum + binary search approach as an alternative.
- Trace through [2,3,1,2,4,3] with target=7 to show the sliding window shrinking.