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.
The Sliding Window approach keeps track of a window using two pointers and dynamically adjusts subarray boundaries to maintain valid subarrays with sums greater than or equal to the target.
1. Initialize two pointers, left and right, both set to the start of the array.
2. Use right to expand the window by including elements in the subarray until the sum is equal to or exceeds the target.
3. Once the sum reaches or exceeds the target, attempt to minimize the window from the left by incrementing left while ensuring the sum remains equal to or greater than the target.
In the C solution, we maintain a running sum of the elements included in the sliding window. We keep incrementing the right pointer to include elements into the subarray. Each time the sum equals or exceeds the target, we check for the minimal length of the valid subarray and decrement elements from the left, reducing the subarray size.
Time Complexity: O(n) where n is the length of the array.
Space Complexity: O(1) because we use a constant amount of extra space.
This approach uses prefix sums and binary search to find the minimal length of subarrays summing to the required target. It builds on the idea that the sum of elements from index i to j can be represented using prefix sums, allowing us to search for valid subarray boundaries efficiently.
1. Compute the prefix sums of the array, which helps us quickly calculate the sum of any subarray.
2. For each starting index, use binary search to find the smallest ending index such that the subarray sum equals or exceeds the target.
In this C solution, we utilize prefix sums and binary search to efficiently locate minimum subarray lengths that meet the target. After constructing the prefix sum array, binary search over this array finds boundaries within a subarray sum condition, reducing it to an efficient search problem.
Time Complexity: O(n log n) due to binary searching for each possible start index.
Space Complexity: O(n) for the prefix sums array.
First, we preprocess the prefix sum array s of the array nums, where s[i] represents the sum of the first i elements of the array nums. Since all elements in the array nums are positive integers, the array s is also monotonically increasing. Also, we initialize the answer ans = n + 1, where n is the length of the array nums.
Next, we traverse the prefix sum array s. For each element s[i], we can find the smallest index j that satisfies s[j] geq s[i] + target by binary search. If j leq n, it means that there exists a subarray that satisfies the condition, and we can update the answer, i.e., ans = min(ans, j - i).
Finally, if ans leq n, it means that there exists a subarray that satisfies the condition, return ans, otherwise return 0.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array nums.
We can use two pointers j and i to maintain a window, where the sum of all elements in the window is less than target. Initially, j = 0, and the answer ans = n + 1, where n is the length of the array nums.
Next, the pointer i starts to move to the right from 0, moving one step each time. We add the element corresponding to the pointer i to the window and update the sum of the elements in the window. If the sum of the elements in the window is greater than or equal to target, it means that the current subarray satisfies the condition, and we can update the answer, i.e., ans = min(ans, i - j + 1). Then we continuously remove the element nums[j] from the window until the sum of the elements in the window is less than target, and then repeat the above process.
Finally, if ans leq n, it means that there exists a subarray that satisfies the condition, return ans, otherwise return 0.
The time complexity is O(n), and the space complexity is O(1). Here, n is the length of the array nums.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: Space Complexity: |
| Binary Search on Prefix Sums | Time Complexity: Space Complexity: |
| Prefix Sum + Binary Search | — |
| Two Pointers | — |
| 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 |
Minimum Size Subarray Sum - Leetcode 209 - Python • NeetCode • 137,853 views views
Watch 9 more video solutions →Practice Minimum Size Subarray Sum with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor