Shortest subarray reaching a sum

You'll build a sliding window that grows and shrinks. The code is short, but it's easy to use where it doesn't work. So most of this lesson explains why each end of the window can move forward and never needs to come back. You need to be comfortable with loops over a list. Related chapter: sliding window.

1. The problem

You get a list of positive integers nums and a positive integer target. Return the length of the shortest subarray whose sum is at least target. A subarray is a run of neighboring numbers. If no subarray works, return 0. This is Minimum Size Subarray Sum (LC 209).

"Subarray" matters: [2, 4, 1] is not a subarray of the first example, because those numbers aren't next to each other. "At least" matters too: the sum can go past the target.

2. A correct baseline

Try every starting index. From each start, extend to the right and keep a running sum. Stop as soon as the sum reaches the target, because extending further from the same start only makes the subarray longer.

def shortest_baseline(nums, target):
    best = 0
    for start in range(len(nums)):
        total = 0
        for end in range(start, len(nums)):
            total += nums[end]
            if total >= target:
                length = end - start + 1
                if best == 0 or length < best:
                    best = length
                break
    return best

assert shortest_baseline([2, 3, 1, 2, 4, 3], 7) == 2
assert shortest_baseline([1, 4, 4], 4) == 1
assert shortest_baseline([1, 1, 1, 1], 11) == 0
assert shortest_baseline([], 3) == 0

This is correct, but it takes O(n²) time in the worst case: the work grows with the square of the list's length. That happens when the target is bigger than the total, so no start stops early. With 100,000 numbers, it's about five billion additions.

The bottleneck. When the outer loop moves from start to start + 1, the inner loop throws away its running sum. Then it adds almost the same numbers again. Worse, it checks end positions that the previous start already ruled out.

3. The observation

In the first example, the shortest subarray starting at index 0 is [2, 3, 1, 2], ending at index 3. Could the subarray starting at index 1 end earlier, at index 2? That would be [3, 1], which sum to 4. But [2, 3, 1] already fell short at 6, and [3, 1] is the same run minus the 2. So it falls short too.

In general: suppose the shortest subarray that works from start ends at end. Then the one from start + 1 must end at or after end. Any earlier end e gives nums[start + 1 .. e], which is nums[start .. e] minus one positive number. That longer run already fell short, so the shorter one does too.

So the right end never needs to move back. Both ends only move forward, and each moves at most n times. That turns the nested search into one pass:

• Move right forward one number at a time, adding it to the window's sum.
• While the sum reaches the target, record the window's length. Then remove nums[left] and move left forward, looking for something shorter.

This works because every number is positive. Adding a number always raises the sum, and removing one always lowers it. So once a window reaches the target, any bigger window does too. And once a window falls short, any smaller window does too.

4. The solution and a trace

def shortest_subarray(nums, target):
    """Length of the shortest contiguous run with sum >= target, or 0.

    Requires every value in nums to be positive.
    """
    best = 0
    left = 0
    window_sum = 0  # always equals sum(nums[left:right + 1])
    for right, value in enumerate(nums):
        window_sum += value
        while window_sum >= target:
            length = right - left + 1
            if best == 0 or length < best:
                best = length
            window_sum -= nums[left]
            left += 1
    return best

assert shortest_subarray([2, 3, 1, 2, 4, 3], 7) == 2
assert shortest_subarray([1, 4, 4], 4) == 1
assert shortest_subarray([1, 1, 1, 1], 11) == 0
assert shortest_subarray([], 3) == 0

Trace the first example with target = 7. A row shows the window after right adds its value, then every shrink step that follows.

The window never tried [2, 3, 1, 2, 4] after it found [2, 3, 1, 2]. Section 3 explains why skipping it is safe.

5. Why it works

Two facts make it work.

The sum is always right. Before each while test, window_sum == sum(nums[left:right + 1]). It starts true for the empty window. Adding nums[right] keeps it true, and so does removing nums[left] as left moves. So every length we record belongs to a real subarray that reaches the target. best is never too small.

The shortest answer always gets recorded. We also need best not to be too large. Say the shortest answer is nums[i .. j]. When right first reaches j, left is still at or before i. That's because left only passes an index after recording a window that starts there. And no window starting at i can reach the target before j, or nums[i .. j] wouldn't be the shortest. So the window contains nums[i .. j] and its sum reaches the target. The while loop keeps recording and shrinking until left passes i, and on the way it records nums[i .. j] itself.

This uses positivity twice. Once to say a window containing nums[i .. j] reaches the target. And once, in section 3, to show right never needs to move back.

6. Cost, edge cases, and failure

Cost. right adds each number once, and left removes each number at most once. So the total work is O(n) despite the nested loop: it grows in step with the list. Extra space is O(1), a fixed amount. To find the cost of a loop like this, count how often each number is added and removed. Multiplying the two loops' lengths overcounts.

Edge cases. An empty list returns 0. One number at least as big as the target gives 1. When the answer is 0, the window grows to the whole list and never shrinks. Python integers don't overflow. In Rust, Java, or C++, use a 64-bit sum when the total can pass 32 bits.

Where it fails. Allow a negative number, and the argument breaks. Take nums = [1, -1, 5] and target = 5. The answer is 1, from [5]. The window reaches sum 5 with [1, -1, 5] and records length 3. Removing 1 drops the sum to 4, so the loop stops shrinking. It never sees that also removing -1 would raise the sum again. For negative numbers, use prefix sums with a monotonic deque instead (LC 862, below).

assert shortest_baseline([1, -1, 5], 5) == 1
assert shortest_subarray([1, -1, 5], 5) == 3  # wrong: the window's argument needs positive values

The code runs without error and returns a believable number. That's why the docstring states the precondition. Passing a few examples doesn't tell you a technique applies; the argument above does.

import random

rng = random.Random(209)
for _ in range(2000):
    nums = [rng.randint(1, 9) for _ in range(rng.randint(0, 12))]
    target = rng.randint(1, 40)
    assert shortest_subarray(nums, target) == shortest_baseline(nums, target), (nums, target)