LeetCode 209 · Sliding window

Minimum Size Subarray Sum, explained with a picture

The shortest stretch with enough light.

Sliding window
▶ Watch it step by step

The problem

Find the length of the shortest block of consecutive numbers whose sum is at least a target. Return 0 if none.

Input:  [2, 3, 1, 2, 4, 3], target = 7
Output: 2   ([4, 3])

Picture it

Picture a window over a row of houses with lit windows. Stretch the right edge until the window has enough light, then pull the left edge in as far as possible while it still has enough. Record the shortest window seen.

Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.

The key idea

Variable sliding window: grow right, shrink left while valid. O(n).

Python solution

def min_len(target, lit):
    left = total = 0
    best = inf
    for right, x in enumerate(lit):
        total += x
        while total >= target:
            best = min(best, right - left + 1)
            total -= lit[left]
            left += 1
    return 0 if best == inf else best

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from math import inf

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.