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] <= 104O(n) solution, try coding another solution of which the time complexity is O(n log(n)).The goal of #209 Minimum Size Subarray Sum is to find the smallest length of a contiguous subarray whose sum is greater than or equal to a target value. Because the array contains only positive integers, we can take advantage of a Sliding Window technique to efficiently adjust the range while maintaining the current sum.
In the optimal strategy, two pointers represent the current window. Expand the window by moving the right pointer and adding elements to the running sum. Whenever the sum becomes greater than or equal to the target, try shrinking the window from the left to minimize its length while still satisfying the condition. This approach ensures every element is processed at most twice.
An alternative method uses Prefix Sum combined with Binary Search. By storing cumulative sums in an array, we can search for the smallest index where the required sum difference is achieved.
The sliding window approach runs in O(n) time with O(1) extra space, making it the most efficient solution for this problem.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sliding Window | O(n) | O(1) |
| Prefix Sum + Binary Search | O(n log n) | O(n) |
NeetCode
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.
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.
1public class Solution {
2 public int minSubArrayLen(int target, int[] nums) {
3 int left = 0The Java solution follows the sliding window pattern using two pointers that slide over the array to dynamically adjust the size of the current subarray to meet the target. The implementation leverages the Math library for minimum comparison operations.
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.
Time Complexity: O(n log n) due to binary searching for each possible start index.
Space Complexity: O(n) for the prefix sums array.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem or its variations appear frequently in technical interviews at top tech companies. It tests understanding of sliding window techniques, prefix sums, and the ability to optimize from brute force to linear time solutions.
The problem mainly relies on two pointers and a running sum rather than complex data structures. For the alternative method, a prefix sum array is used to support efficient binary searches on cumulative values.
The optimal approach uses the sliding window technique. Since all numbers in the array are positive, we can expand and shrink a window while maintaining the running sum. This allows us to find the minimal subarray length in O(n) time.
Yes, a combination of prefix sums and binary search can solve the problem. After building a prefix sum array, binary search can locate the smallest index that satisfies the required sum difference. This approach runs in O(n log n) time.
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.