Minimum Size Subarray Sum
MedPrompt
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: 1Example 3:
Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0
Constraints:
1 <= target <= 1091 <= nums.length <= 1051 <= nums[i] <= 104
Follow up: If you have figured out the
O(n) solution, try coding another solution of which the time complexity is O(n log(n)).Approaches
3 approaches with complexity analysis and trade-offs.
Check all possible subarrays and find the minimum length subarray with sum greater than or equal to target.
Algorithm
- Initialize minLength as Integer.MAX_VALUE
- For each index i from 0 to n-1:
- Initialize sum as 0
- For each index j from i to n-1:
- Add nums[j] to sum
- If sum >= target:
- Update minLength if current length (j-i+1) is smaller
- Break inner loop
- Return 0 if minLength is still Integer.MAX_VALUE, else return minLength
Walkthrough
For each index i, we try all possible subarrays starting from i and calculate their sum. If we find a sum that is greater than or equal to target, we update the minimum length if the current subarray length is smaller.
class Solution { public int minSubArrayLen(int target, int[] nums) { int n = nums.length; int minLength = Integer.MAX_VALUE; for (int i = 0; i < n; i++) { int sum = 0; for (int j = i; j < n; j++) { sum += nums[j]; if (sum >= target) { minLength = Math.min(minLength, j - i + 1); break; } } } return minLength == Integer.MAX_VALUE ? 0 : minLength; }}Complexity
Time
O(n²) where n is the length of the array as we need to check all possible subarrays
Space
O(1) as we only use a constant amount of extra space
Trade-offs
Pros
Simple to understand and implement
Works for all test cases
Cons
Very inefficient for large arrays
Time complexity is quadratic
Use prefix sum array and binary search to find the minimum length subarray.
Algorithm
- Create prefix sum array
- For each index i from 0 to n-1:
- Use binary search to find smallest index j where sum[i:j] >= target
- Update minLength if current length is smaller
- Return 0 if minLength is still Integer.MAX_VALUE, else return minLength
Walkthrough
We first create a prefix sum array. For each index i, we use binary search to find the smallest index j where the sum of subarray from i to j is greater than or equal to target.
class Solution { public int minSubArrayLen(int target, int[] nums) { int n = nums.length; int[] prefixSum = new int[n + 1]; // Calculate prefix sum for (int i = 1; i <= n; i++) { prefixSum[i] = prefixSum[i-1] + nums[i-1]; } int minLength = Integer.MAX_VALUE; for (int i = 0; i < n; i++) { int toFind = target + prefixSum[i]; int index = binarySearch(prefixSum, toFind, i+1, n); if (index != -1) { minLength = Math.min(minLength, index - i); } } return minLength == Integer.MAX_VALUE ? 0 : minLength; } private int binarySearch(int[] prefixSum, int target, int left, int right) { while (left <= right) { int mid = left + (right - left) / 2; if (prefixSum[mid] >= target) { right = mid - 1; } else { left = mid + 1; } } return left <= prefixSum.length - 1 ? left : -1; }}Complexity
Time
O(n log n) where n is the length of the array as we perform binary search for each index
Space
O(n) to store the prefix sum array
Trade-offs
Pros
More efficient than brute force approach
Works well for sorted prefix sums
Cons
Requires extra space for prefix sum array
Not as efficient as the sliding window approach
Use two pointers to maintain a sliding window and find the minimum length subarray.
Algorithm
- Initialize left pointer, sum and minLength
- For each right pointer from 0 to n-1:
- Add nums[right] to sum
- While sum >= target:
- Update minLength if current length is smaller
- Subtract nums[left] from sum
- Increment left pointer
- Return 0 if minLength is still Integer.MAX_VALUE, else return minLength
Walkthrough
We use two pointers, left and right, to maintain a window. We expand the window by moving right pointer when sum < target and shrink it by moving left pointer when sum >= target.
class Solution { public int minSubArrayLen(int target, int[] nums) { int n = nums.length; int left = 0; int sum = 0; int minLength = Integer.MAX_VALUE; for (int right = 0; right < n; right++) { sum += nums[right]; while (sum >= target) { minLength = Math.min(minLength, right - left + 1); sum -= nums[left]; left++; } } return minLength == Integer.MAX_VALUE ? 0 : minLength; }}Complexity
Time
O(n) where n is the length of the array as we traverse the array once with two pointers
Space
O(1) as we only use a constant amount of extra space
Trade-offs
Pros
Most efficient solution with linear time complexity
Uses constant extra space
Single pass through the array
Cons
Might be slightly harder to understand compared to brute force
Both pointers only move forward, so we might miss some edge cases if not implemented carefully
Solutions
Solution
public class Solution { public int MinSubArrayLen(int target, int[] nums) { int n = nums.Length; long s = 0; int ans = n + 1; for (int i = 0, j = 0; i < n; ++i) { s += nums[i]; while (s >= target) { ans = Math.Min(ans, i - j + 1); s -= nums[j++]; } } return ans == n + 1 ? 0 : ans; }}class Solution {public int minSubArrayLen(int target, int[] nums) { int n = nums.length; long s = 0; int ans = n + 1; for (int i = 0, j = 0; i < n; ++i) { s += nums[i]; while (j < n && s >= target) { ans = Math.min(ans, i - j + 1); s -= nums[j++]; } } return ans <= n ? ans : 0; }}class Solution: def minSubArrayLen(self, target: int, nums: List[int]) -> int: n = len(nums) ans = n + 1 s = j = 0 for i, x in enumerate(nums): s += x while j < n and s >= target: ans = min(ans, i - j + 1) s -= nums[j] j += 1 return ans if ans <= n else 0class Solution {public: int minSubArrayLen(int target, vector<int> &nums) { int n = nums.size(); long long s = 0; int ans = n + 1; for (int i = 0, j = 0; i < n; ++i) { s += nums[i]; while (j < n && s >= target) { ans = min(ans, i - j + 1); s -= nums[j++]; } } return ans == n + 1 ? 0 : ans; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.