Given an array of positive integers nums and a positive integer target, return the length of the shortest contiguous subarray whose sum is at least target. If no subarray reaches target, return 0.
Example 1
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
The subarray
[4,3] sums to 7 and no single element reaches 7.Example 2
Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0
Even the whole array only sums to 8.
Constraints
- 1 <= target <= 10^9
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^4
Hints
Frequently asked at: Google, Amazon, Meta, Goldman Sachs
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Trying every start and end is O(n^2). Because every value is positive, the window sum grows when we extend right and shrinks when we move left. So for each right end, we can keep moving the left end forward while the sum stays at least target; each time we have a valid window and record its length. Both ends only move forward, so the total work is O(n).
Algorithm
- Set
left = 0,sum = 0,best = infinity. - For each
right, addnums[right]tosum. - While
sum >= target: updatebestwithright - left + 1, subtractnums[left], moveleftright. - Return
best, or0if it was never updated.
Time:
O(n)Space: O(1)Interview tip: The sliding window only works because values are positive. With negative numbers you need prefix sums with a monotonic deque. A common follow-up asks for an O(n log n) solution: binary search on prefix sums.
class Solution: def minSubArrayLen(self, target: int, nums: List[int]) -> int: left = total = 0 best = float('inf') for right, x in enumerate(nums): total += x while total >= target: # valid window: record it and shrink best = min(best, right - left + 1) total -= nums[left] left += 1 return 0 if best == float('inf') else bestCtrl + Enter runs the examples