Watch 10 video solutions for Minimum Size Subarray Sum, a medium level problem involving Array, Binary Search, Sliding Window. This walkthrough by NeetCode has 266,725 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an array of positive integers nums and a positive integer target, 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.
Example 1:
Input: target = 7, nums = [2,3,1,2,4,3] Output: 2 Explanation: The subarray [4,3] has the minimal length under the problem constraint.
Example 2:
Input: target = 4, nums = [1,4,4] Output: 1
Example 3:
Input: target = 11, nums = [1,1,1,1,1,1,1,1] Output: 0
Constraints:
1 <= target <= 1091 <= nums.length <= 1051 <= nums[i] <= 104Follow up: If you have figured out the
O(n) solution, try coding another solution of which the time complexity is O(n log(n)).Problem Overview: Given an array of positive integers and a target value, find the minimum length of a contiguous subarray whose sum is greater than or equal to the target. If no such subarray exists, return 0. The challenge is identifying the shortest valid window without checking every possible subarray.
Approach 1: Sliding Window (O(n) time, O(1) space)
This problem becomes straightforward once you recognize that all numbers are positive. That property allows a sliding window technique. Maintain two pointers: left and right. Expand the window by moving right and adding elements to a running sum. Whenever the sum becomes greater than or equal to the target, shrink the window from the left while the condition still holds. Each shrink step updates the minimum length. Because each element enters and leaves the window at most once, the algorithm runs in O(n) time with O(1) extra space. This approach is the most efficient and widely expected in interviews when dealing with positive-number subarray problems.
Approach 2: Binary Search on Prefix Sums (O(n log n) time, O(n) space)
Another strategy uses prefix sums combined with binary search. First compute a prefix array where prefix[i] stores the sum of the first i elements. For each index i, you want the smallest index j such that prefix[j] - prefix[i] ≥ target. Rearranging gives prefix[j] ≥ prefix[i] + target. Since the prefix array is strictly increasing (due to positive numbers), you can binary search for this value. The difference j - i represents the subarray length, and you track the minimum across all i. Building the prefix array takes O(n), and performing a binary search for each index results in O(n log n) time and O(n) space.
The binary search method is conceptually useful because it generalizes to other problems where monotonic prefix structures exist. However, it introduces additional memory and logarithmic overhead compared to the linear sliding window.
Recommended for interviews: The sliding window solution is the expected answer. It shows you recognize how positive numbers guarantee that shrinking the window only decreases the sum, making the two‑pointer strategy correct. Mentioning the prefix sum + binary search approach demonstrates deeper algorithm knowledge, but the O(n) sliding window approach is what most interviewers want to see for this array problem.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window | O(n) | O(1) | Best general solution when array contains positive integers |
| Binary Search on Prefix Sums | O(n log n) | O(n) | Useful when applying prefix sums with searchable monotonic structures |