Minimum Size Subarray Sum

Medium#209variable size

You get an array of positive numbers and a target. Find the length of the shortest run of numbers in a row whose sum is at least the target, or 0 if there is none. Our example: [3, 1, 4, 2, 6, 5, 1] and target = 11 — the answer is 2: 6 + 5 = 11.

209 Minimum Size Subarray SumWalkthrough · 1×

Example: [3, 1, 4, 2, 6, 5, 1], target = 11. A good window, with a sum of at least 11, is drawn as found.

03112432465561sum0target11best–
not reached yetwindownumber coming innumber going outleft the windowgood window

The window is empty: sum = 0

01/46
restart · back · play · step
Speed
1function minSubArrayLen(target, nums):
2 sum = 0
3 left = 0
4 best = infinity
5 for right from 0 to len(nums) - 1:
6 sum = sum + nums[right]
7 while sum >= target:
8 best = min(best, right - left + 1)
9 sum = sum - nums[left]
10 left = left + 1
11 if best == infinity:
12 return 0
13 return best
state
sum
0
left
–
right
–
best
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. All numbers are positive, so a longer window has a bigger sum. Once a window is good, every longer window with the same right end is good too, but none of them is shorter: the only ones worth checking come from shrinking.
  2. The length is recorded while shrinking, at each good window, and shrinking goes on until the sum drops below the target. So for every right the shortest good window ending there is measured.
  3. Dropping the number at left is safe: the window from left to right was good and is already measured, and a later window starting at the same left would end further right, so it could only be longer.

Complexity

Time O(n): right passes each number once and left passes each number at most once, so the inner loop runs at most n times in all. Memory O(1).

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.