Skip to content
Work Free practice Coding course Blog Method Results Why me About Enquire Book a call

Coding · Sliding window

Understanding the problem

Lesson · 7 min read · Sliding window

The cost of trying every run

Take a list of positive numbers and ask for the longest run of consecutive entries whose sum is at most K. The first solution anyone writes tries every start and every end:

best = 0
for i in range(n):
    total = 0
    for j in range(i, n):
        total += a[j]
        if total <= K:
            best = max(best, j - i + 1)

Keeping a running total already saves a factor of n over recomputing each sum, but there are still about n²/2 pairs (i, j) to visit.

Length of listRuns examinedAt 10⁸ steps a second
1,000≈ 500,000instant
100,000≈ 5 billionabout a minute
1,000,000≈ 500 billionwell over an hour

Most of those runs are hopeless, and the double loop has no way of knowing. A run that starts at i and already sums to more than K cannot become valid by growing, yet the inner loop keeps extending it to the end of the list.

The property that saves the work

With positive numbers, two facts hold. Adding an element on the right can only increase the sum. Removing one on the left can only decrease it. So if the run [lo, hi] is too big, every longer run containing it is too big as well, and the only repair is to move lo right. And once lo has moved past an index, no later window will want it back: a window starting further left would contain the one that was already too big.

That is the whole argument. Both ends move only forward, each index enters the window once and leaves at most once, and the total work is at most 2n steps.

The longest run with sum at most 5 in [3, 1, 2, 1, 4, 1, 1]. Watch the left edge: it only ever moves right.

  1. Step 1 / 7
    nums
    30lo/hi112213441516
    sum3best1

    Add 3 on the right: the window [0, 0] sums to 3. New longest: 1.

  2. Step 2 / 7
    nums
    30lo11hi2213441516
    sum4best2

    Add 1 on the right: the window [0, 1] sums to 4. New longest: 2.

  3. Step 3 / 7
    nums
    3011lo22hi13441516
    sum3best2

    Add 2 on the right: the window [0, 2] sums to 6. That is over 5, so drop 3 from the left; the sum is now 3.

  4. Step 4 / 7
    nums
    3011lo2213hi441516
    sum4best3

    Add 1 on the right: the window [1, 3] sums to 4. New longest: 3.

  5. Step 5 / 7
    nums
    30112213lo44hi1516
    sum5best3

    Add 4 on the right: the window [1, 4] sums to 8. That is over 5, so drop 1 then 2 from the left; the sum is now 5.

  6. Step 6 / 7
    nums
    3011221344lo15hi16
    sum5best3

    Add 1 on the right: the window [3, 5] sums to 6. That is over 5, so drop 1 from the left; the sum is now 5.

  7. Step 7 / 7
    nums
    301122134415lo16hi
    sum2best3

    Add 1 on the right: the window [4, 6] sums to 6. That is over 5, so drop 4 from the left; the sum is now 2. The scan is over: the longest run with sum at most 5 has length 3.

Where it breaks: negative numbers

The argument used positivity twice, and without it the method gives wrong answers, not slow ones. Ask for the shortest run with sum at least 8 in [1, −5, 4, 4]. The answer is [4, 4], length 2. A sliding window adds 1, then −5, then 4, then 4, reaching a running total of 4 and never 8, so it reports that no run exists.

The window failed because shrinking from the left could have raised the sum by dropping the −5. When an element can move the sum in either direction, the window's invariant is gone. That problem needs prefix sums, and a monotonic queue of candidate starts, instead.

Before reaching for a window, say the invariant out loud: "if this window is invalid, so is every larger one". If you cannot say it truthfully, the window is the wrong tool.