Minimum Size Subarray Sum
Shortest contiguous subarray with sum ≥ target via expanding/contracting window over positive integers.
3 min read
sliding-window array
Problem#
Given an array of positive integers nums and a target, return the minimal length of a contiguous subarray whose sum is at least target. Return 0 if none.
Examples#
target = 7, nums = [2,3,1,2,4,3]→2([4,3])target = 11, nums = [1,1,1,1,1,1,1,1]→0
Constraints#
- All elements positive.
Approach#
Expand right to grow the sum. Whenever sum ≥ target, shrink left while still valid, recording the shortest.
Solution#
class Solution {public: int minSubArrayLen(int target, vector<int>& nums) { int left = 0, sum = 0, best = INT_MAX; for (int right = 0; right < (int)nums.size(); ++right) { sum += nums[right]; while (sum >= target) { best = min(best, right - left + 1); sum -= nums[left++]; } } return best == INT_MAX ? 0 : best; }};func minSubArrayLen(target int, nums []int) int { left, sum, best := 0, 0, math.MaxInt32 for right := 0; right < len(nums); right++ { sum += nums[right] for sum >= target { if right-left+1 < best { best = right - left + 1 } sum -= nums[left] left++ } } if best == math.MaxInt32 { return 0 } return best}from typing import List
class Solution: def minSubArrayLen(self, target: int, nums: List[int]) -> int: left = 0 s = 0 best = float('inf') for right in range(len(nums)): s += nums[right] while s >= target: best = min(best, right - left + 1) s -= nums[left] left += 1 return 0 if best == float('inf') else int(best)function minSubArrayLen(target, nums) { let left = 0, sum = 0, best = Infinity; for (let right = 0; right < nums.length; right++) { sum += nums[right]; while (sum >= target) { best = Math.min(best, right - left + 1); sum -= nums[left++]; } } return best === Infinity ? 0 : best;}class Solution { public int minSubArrayLen(int target, int[] nums) { int left = 0, sum = 0, best = Integer.MAX_VALUE; for (int right = 0; right < nums.length; right++) { sum += nums[right]; while (sum >= target) { best = Math.min(best, right - left + 1); sum -= nums[left++]; } } return best == Integer.MAX_VALUE ? 0 : best; }}function minSubArrayLen(target: number, nums: number[]): number { let left = 0, sum = 0, best = Infinity; for (let right = 0; right < nums.length; right++) { sum += nums[right]; while (sum >= target) { best = Math.min(best, right - left + 1); sum -= nums[left++]; } } return best === Infinity ? 0 : best;}Editorial#
Positivity matters: with negatives, a window’s sum is non-monotonic in length, so shrinking left wouldn’t preserve the search invariant. For arrays with negatives, prefix-sum + sorted structures or deque give an O(n log n) / O(n) alternative.
Complexity#
- Time: O(n) (each pointer advances ≤ n times).
- Space: O(1).
Concept revision#
Related#