Shortest satisfying window

57 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

In 2, 3, 1, 2, 4, 3 find the shortest stretch of consecutive numbers whose sum is at least 7. By hand you check lengths from short to long: any single number ≥ 7? No. Any pair? 4 + 3 = 7, yes, so the answer is 2.

Checking every stretch is O(n²) sums. The longest-window pattern grows the right end and shrinks the left end only when forced. Here the question is flipped: we want the shortest window that satisfies a condition, so the shrinking must be eager, not reluctant.

Build the structure, one piece at a time

Piece one: a window [l, r] and a running sum of its contents, all numbers being positive.

Piece two: grow r until the window satisfies the condition (sum ≥ 7). Before that there is nothing to record.

Piece three: while the window still satisfies, record its length and then shrink from the left. Shrinking as far as possible is what finds the shortest window ending at this r. When the window stops satisfying, go back to growing.

With a different condition the aggregate changes but the two loops do not: for "shortest substring containing all letters of a pattern", the aggregate is a count table plus a "missing" counter, and "satisfies" means missing = 0.

Why it is correct

The invariant at the moment we record a length: [l, r] satisfies the condition (we only record inside the "while it satisfies" loop), and when we leave that loop [l, r] no longer satisfies, so no window ending at r and starting at or after l satisfies either, because shrinking a satisfying window of positive numbers can only lower the sum. Combined, for each r the shortest satisfying window ending at r was recorded, because we recorded every window from the first satisfying one down to the last satisfying one. Taking the minimum over all r gives the shortest overall. The property needed is the mirror of the longest-window case: if a window satisfies, every larger window containing it satisfies too (sums only grow with positive numbers; a superset still contains all required letters).

Why it is fast

r moves right n times and l moves right at most n times in total, since it never retreats and never passes r. Every move is one addition or subtraction on the aggregate:

≤ 2n pointer moves, O(n) time

against O(n²) for checking every stretch. The eager shrinking does not cost extra, because each element leaves the window at most once.

How to recognise it in an interview

Cues: "shortest", "minimum length", "smallest window", together with a condition that keeps holding when the window grows ("sum at least", "contains all of", "covers"). If the numbers can be negative, the sum is no longer monotone and this pattern fails; that is when a monotonic deque or prefix sums are needed instead.

Say: "I will grow the right end until the window satisfies, then shrink the left end while it still satisfies, recording lengths as I go." Minimum Size Subarray Sum is the example. Minimum Window Substring is the same loop with a need-count table and a missing counter, recording the shortest window whenever missing is zero.

02The idea in one line

Grow right until the window satisfies; shrink left while it still does.

Reach for it when: Minimum window substring, minimum size subarray sum.

Cost: O(n) time.

03The walk-through, step by step

The video works one example: Minimum Size Subarray Sum ≥ 7 on [2,3,1,2,4,3]. These are its captions in order, so you can follow without the video or check a step you missed.

1. Grow r until the sum reaches the target, then shrink l while it still does
2. Add nums[0] = 2: sum = 2 < 7, keep growing
3. Add nums[1] = 3: sum = 5 < 7, keep growing
4. Add nums[2] = 1: sum = 6 < 7, keep growing
5. Add nums[3] = 2: sum = 8 ≥ 7, now shrink
6. [0..3] sums to 8 ≥ 7 with length 4: best = 4; drop nums[0]
7. Add nums[4] = 4: sum = 10 ≥ 7, now shrink
8. [1..4] sums to 10 ≥ 7 with length 4: best = 4; drop nums[1]
9. [2..4] sums to 7 ≥ 7 with length 3: best = 3; drop nums[2]
10. Add nums[5] = 3: sum = 9 ≥ 7, now shrink
11. [3..5] sums to 9 ≥ 7 with length 3: best = 3; drop nums[3]
12. [4..5] sums to 7 ≥ 7 with length 2: best = 2; drop nums[4]
13. Shortest window: [4..5] = [4, 3] → 2
14. Both pointers move right only: O(n)

04Asked at Google

5 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Sliding Window: Fixed-size window, Longest valid window, Count windows via at-most(k) trick, Window with a need-counter.