Watch 10 video solutions for Minimum Size Subarray Sum, a medium level problem involving Array, Binary Search, Sliding Window. This walkthrough by NeetCode has 137,853 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 minimizing the length while keeping the running sum ≥ target.
Approach 1: Brute Force Enumeration (O(n²) time, O(1) space)
Check every possible starting index and expand the subarray to the right while maintaining a running sum. As soon as the sum becomes ≥ target, record the length and stop expanding that starting point. This approach uses nested loops and repeatedly recomputes partial sums. It works for small arrays but quickly becomes slow because the worst case evaluates nearly every subarray.
Approach 2: Sliding Window / Two Pointers (O(n) time, O(1) space)
The optimal solution uses the sliding window technique. Because all numbers are positive, expanding the right pointer always increases the sum, and shrinking the left pointer always decreases it. Maintain two pointers left and right with a running sum. Expand right until the sum ≥ target, then shrink from the left while the condition still holds to minimize the window size. Each element enters and leaves the window at most once, producing linear time complexity. This approach is the standard solution for array problems involving contiguous segments with positive numbers.
Approach 3: Binary Search on Prefix Sums (O(n log n) time, O(n) space)
Build a prefix sum array where prefix[i] stores the sum of the first i elements. For each starting index i, you need the smallest index j such that prefix[j] - prefix[i] ≥ target. Since the prefix array is strictly increasing with positive numbers, you can apply binary search to find that index efficiently. Compute the candidate subarray length j - i and track the minimum. This method is useful when you want a systematic approach using prefix sums, though it is slower than sliding window.
Recommended for interviews: The sliding window solution is the expected answer. Interviewers want to see that you recognize the positive-number constraint and convert the problem into a dynamic window that expands and contracts. Mentioning the brute force approach first demonstrates baseline reasoning, but implementing the O(n) sliding window shows strong algorithmic pattern recognition.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n²) | O(1) | Conceptual baseline or very small arrays |
| Sliding Window | O(n) | O(1) | Optimal approach when array elements are positive |
| Binary Search on Prefix Sums | O(n log n) | O(n) | When using prefix sums or demonstrating binary search technique |