Minimum Size Subarray Sum
Problem
Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray of which the sum is at least target. If there is no such subarray, return 0.
- 1 ≤ target ≤ 10⁹
- 1 ≤ nums.length ≤ 10⁵
- 1 ≤ nums[i] ≤ 10⁵
Example
target = 7, nums = [2,3,1,2,4,3]2The brute-force approach would check every possible subarray, summing elements and comparing to target, which is O(n²) and inefficient. The optimal approach uses a sliding window to maintain a running sum of a contiguous subarray. Starting with both pointers at the beginning, the window expands by moving the right pointer and adding elements until the sum reaches or exceeds the target. Then, the window contracts from the left to find the smallest valid subarray. For the example, the window first expands to include [2,3,1,2] with sum 8, then contracts from the left to [4,3] with sum 7, which has length 2, the minimal length.
Approach
Straightforward Solution
A brute-force solution checks all subarrays, summing each, resulting in O(n²) time complexity, which is too slow for large inputs.
Core Observation
The problem requires finding the shortest contiguous subarray with sum at least target. Because all numbers are positive, the sum of the window strictly increases when expanding right and strictly decreases when contracting left, enabling a two-pointer sliding window approach.
Path to Optimal
The key insight is that with positive integers, the sum of a window increases as the right pointer moves forward and decreases as the left pointer moves forward. This monotonic behavior allows a sliding window to expand until the sum meets or exceeds the target, then contract to find the minimal length subarray that satisfies the condition. This approach reduces the complexity to O(n) because each element is visited at most twice.
Optimal Approach
Use two pointers, left and right, to define a sliding window. Expand right pointer, adding nums[right] to the window sum. When the sum is at least target, update the minimal length and contract the window from the left by subtracting nums[left] and moving left forward. Repeat until right reaches the end. Return 0 if no valid subarray is found.
Time
O(n)
Each element is visited at most twice: once when the right pointer expands the window and once when the left pointer contracts it, resulting in linear time.
Space
O(1)
Only a few variables are used to track pointers and sums, with no additional data structures proportional to input size.
Pattern Spotlight
Sliding Window (Variable Size Window)
When dealing with contiguous subarrays and a sum or condition that can be incrementally updated, use two pointers to expand and contract the window dynamically, exploiting monotonic properties to achieve O(n) time.
Solution
| 1 | class Solution: |
| 2 | def minSubArrayLen(self, target: int, nums: List[int]) -> int: |
| 3 | res = float("inf") |
| 4 | left = 0 |
| 5 | window_sum = 0 |
| 6 | |
| 7 | for right, value in enumerate(nums): |
| 8 | window_sum += value |
| 9 | while window_sum >= target: |
| 10 | res = min(res, right - left + 1) |
| 11 | window_sum -= nums[left] |
| 12 | left += 1 |
| 13 | |
| 14 | return 0 if res == float("inf") else res |
| 1 | import java.util.*; |
| 2 | |
| 3 | class Solution { |
| 4 | public int minSubArrayLen(int target, int[] nums) { |
| 5 | int res = Integer.MAX_VALUE; |
| 6 | int left = 0; |
| 7 | int window_sum = 0; |
| 8 | |
| 9 | for (int right = 0; right < nums.length; right++) { |
| 10 | window_sum += nums[right]; |
| 11 | while (window_sum >= target) { |
| 12 | res = Math.min(res, right - left + 1); |
| 13 | window_sum -= nums[left]; |
| 14 | left++; |
| 15 | } |
| 16 | } |
| 17 | |
| 18 | return res == Integer.MAX_VALUE ? 0 : res; |
| 19 | } |
| 20 | } |
| 1 | #include <vector> |
| 2 | #include <algorithm> |
| 3 | #include <climits> |
| 4 | |
| 5 | using namespace std; |
| 6 | |
| 7 | class Solution { |
| 8 | public: |
| 9 | int minSubArrayLen(int target, vector<int>& nums) { |
| 10 | int res = INT_MAX; |
| 11 | int left = 0; |
| 12 | int window_sum = 0; |
| 13 | |
| 14 | for (int right = 0; right < (int)nums.size(); right++) { |
| 15 | window_sum += nums[right]; |
| 16 | while (window_sum >= target) { |
| 17 | res = min(res, right - left + 1); |
| 18 | window_sum -= nums[left]; |
| 19 | left++; |
| 20 | } |
| 21 | } |
| 22 | |
| 23 | return res == INT_MAX ? 0 : res; |
| 24 | } |
| 25 | }; |
| 1 | var minSubArrayLen = function(target, nums) { |
| 2 | let res = Infinity; |
| 3 | let left = 0; |
| 4 | let window_sum = 0; |
| 5 | |
| 6 | for (let right = 0; right < nums.length; right++) { |
| 7 | window_sum += nums[right]; |
| 8 | while (window_sum >= target) { |
| 9 | res = Math.min(res, right - left + 1); |
| 10 | window_sum -= nums[left]; |
| 11 | left++; |
| 12 | } |
| 13 | } |
| 14 | |
| 15 | return res === Infinity ? 0 : res; |
| 16 | }; |
Step-by-Step Solution
Initialize Sliding Window State and Result
| 3 | res = float("inf") |
| 4 | left = 0 |
| 5 | window_sum = 0 |
Objective
To set up variables for tracking the minimal subarray length, the left pointer, and the current window sum.
Key Insight
Initializing the result to infinity allows easy comparison to find the minimal length. The left pointer starts at zero to represent the window's start, and the window sum starts at zero to accumulate values as the window expands. This setup is essential for the sliding window to function correctly.
Interview Quick-Check
Core Logic
Initializing result to infinity ensures any valid subarray length found will replace it, enabling minimal length tracking.
State & Boundaries
Starting left pointer at zero and window sum at zero correctly represents an empty window before iteration.
Expand Window and Contract to Find Minimal Length
| 7 | for right, value in enumerate(nums): |
| 8 | window_sum += value |
| 9 | while window_sum >= target: |
| 10 | res = min(res, right - left + 1) |
| 11 | window_sum -= nums[left] |
| 12 | left += 1 |
Objective
To iterate through the array with the right pointer, expanding the window sum, and contract from the left when the sum meets or exceeds the target to minimize the window size.
Key Insight
The sliding window expands by adding the current right element to the sum. When the sum reaches or exceeds the target, the window contracts from the left to find the smallest valid subarray. This contraction is possible because all numbers are positive, so removing elements from the left decreases the sum, allowing the algorithm to find the minimal length efficiently without missing any valid subarrays.
Interview Quick-Check
Core Logic
The algorithm expands the window by moving right and adding to the sum, then contracts by moving left and subtracting from the sum whenever the sum is sufficient.
State & Boundaries
The while loop condition ensures contraction only happens when the window sum is at least the target.
Common Pitfalls & Bugs
Failing to update the minimal length inside the contraction loop or incorrect pointer updates can lead to wrong answers or infinite loops.
Complexity
Each element is processed at most twice, once when added and once when removed, ensuring O(n) time complexity.
Return Result or Zero if No Valid Subarray Found
| 14 | return 0 if res == float("inf") else res |
Objective
To return the minimal length found or zero if no subarray meets the target sum.
Key Insight
If the result remains infinity, it means no valid subarray was found, so returning zero correctly signals this. Otherwise, returning the minimal length found completes the solution.
Interview Quick-Check
Core Logic
Returning zero when no valid subarray is found aligns with the problem requirement.
State & Boundaries
The ternary conditional cleanly handles the edge case without extra branching.
Line Analysis
This solution has 1 Critical line interviewers watch for.
while window_sum >= target:While the window sum is at least the target, attempt to contract the window.
This while loop is the core of the sliding window technique; it contracts the window only when the sum condition is met, ensuring minimal length subarrays are found without missing any valid candidates.
res = float("inf")Initialize the result variable to infinity to track the minimal subarray length.
Setting result to infinity allows any found subarray length to replace it, enabling straightforward minimal length comparisons.
res = min(res, right - left + 1)Update the result with the minimal length between current and new window size.
Tracking the minimal window length here guarantees the smallest valid subarray length is recorded as the window contracts.
window_sum -= nums[left]Subtract the leftmost element from the window sum to contract the window.
Removing the left element decreases the sum, allowing the window to shrink while maintaining the sum condition for further minimal length checks.
window_sum += valueAdd the current value to the window sum.
Incrementally updating the window sum maintains the total of the current subarray, enabling efficient sum checks.
left += 1Move the left pointer forward to reflect window contraction.
Advancing the left pointer updates the window boundaries correctly, enabling the next iteration to consider a smaller subarray.
return 0 if res == float("inf") else resReturn zero if no valid subarray was found; otherwise, return the minimal length.
This conditional return cleanly handles the edge case where no subarray meets the target, fulfilling the problem's requirement.
for right, value in enumerate(nums):Iterate through the array with the right pointer and current value.
Enumerating both index and value enables dynamic window expansion and sum updates in a single pass.
left = 0Initialize the left pointer of the sliding window to zero.
Starting the left pointer at zero correctly represents the beginning of the window before iteration.
window_sum = 0Initialize the window sum to zero.
Starting with a zero sum accurately reflects an empty window, allowing incremental sum updates as the window expands.
Test Your Understanding
Why does the sliding window approach work efficiently only because the array contains positive integers?
Because positive integers ensure the window sum strictly increases when expanding right and strictly decreases when contracting left, allowing the window to move forward without missing any valid subarrays and guaranteeing O(n) time.
Related Problems
Sliding Window pattern
Don't just read it. Drill it.
Reconstruct Minimum Size Subarray Sum from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Minimum Size Subarray Sum drill