Sliding Window Explained Visually: From O(n·k) to O(n)

Sliding window is what you get when you stop recomputing something you already know. It is one of the cheapest upgrades in all of algorithm work: the brute force and the optimal solution have nearly identical structure, and the difference between them is two lines.

The problem it solves

Given an array and a window length k, find the largest sum of any k consecutive values.

The direct approach is one sum per starting position: n windows, k additions each, O(n·k). On a long array with a wide window that is quadratic in everything but name.

Look at what it repeats. The window starting at index 0 and the window starting at index 1 share k-1 of their k values. The second sum recomputes almost the entire first one.

The intuition

Do not rebuild the window. Move it.

Compute the first window's sum once. Then, to slide one step right, add the value entering on the right and subtract the value leaving on the left. Two operations, regardless of how wide the window is.

That is it. The sum is now a piece of state that travels with the window instead of a quantity you derive from scratch, and the total cost drops from O(n·k) to O(n) — one addition and one subtraction per position.

The same trick generalises to anything you can add and remove incrementally: a count, a frequency table, a maximum with the right structure. If a quantity can be updated at both edges in constant time, it can slide.

Watch it run

The coral block is the current window. Watch the two readouts: one is the live window value, the other is the best seen so far. Notice that the window value changes by exactly two elements' worth per step, never k.

The brute-force version would light up all k cells again on every single step. The window lights up two.

The code

def max_window_sum(nums, k):
    """Largest sum of k consecutive values, in one pass."""
    if k > len(nums):
        return None
    window = sum(nums[:k])              # the first window, built once
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]  # enter on the right, leave on the left
        best = max(best, window)
    return best

print(max_window_sum([4, -1, 2, 7, 3, -5, 6], 3))   # 12   -> 2 + 7 + 3
print(max_window_sum([1, 2], 5))                    # None

One loop, O(n) time, O(1) space. Compare it line by line with the nested-loop version and the only real difference is that sum() moved outside the loop.

The variable-size version

Fixed k is the warm-up. The questions that actually get asked sound like "the longest substring with no repeated characters" — the window's length is not given, it is the answer.

The shape changes slightly: the right edge always advances, and the left edge advances only far enough to restore the property the window must satisfy.

def longest_unique(text):
    """Length of the longest run with no repeated character."""
    last_seen = {}
    start = best = 0
    for end, ch in enumerate(text):
        # A repeat INSIDE the window means the left edge must jump past it.
        if ch in last_seen and last_seen[ch] >= start:
            start = last_seen[ch] + 1
        last_seen[ch] = end
        best = max(best, end - start + 1)
    return best

print(longest_unique("abcabcbb"))   # 3   -> "abc"
print(longest_unique("bbbbb"))      # 1   -> "b"
print(longest_unique("pwwkew"))     # 3   -> "wke"

Where it goes wrong

• last_seen[ch] >= start is not optional. Without it, a character last seen before the window would drag start backwards, and the window would grow when it should not. This is the single most common bug in this pattern.
• Windows and negative numbers. The fixed-size version handles them fine. A variable-size "largest sum at least k" does not, because shrinking the window no longer reliably lowers the sum — the monotonicity the shrink step depends on is gone. That is a prefix-sum question, not a window one.
• k larger than the array. Decide what that means and say so. Returning None, as above, is a choice; crashing is not.
• Rebuilding state inside the loop. Calling sum(nums[i:i+k]) or len(set(window)) per step puts the O(k) straight back. If you see a slice inside the loop, the window has stopped sliding.
• Off-by-one in the length. The window [start, end] is inclusive at both ends, so its length is end - start + 1. Getting this wrong reports every answer one short.

How to say it in an interview

Name the redundancy before you name the technique:

"Consecutive windows overlap in k-1 elements, so recomputing each sum repeats work I already did. I will keep the window's sum as state and update it at the edges — add the entering value, subtract the leaving one — which makes each step constant and the whole scan O(n) time with O(1) space, down from O(n·k). For the variable-length version the right edge always advances and the left edge only moves to restore the constraint; neither goes backwards, so it is still linear."

Then write the loop. If the interviewer follows up with "what if the values can be negative", you already know that is a different question — and saying so is the answer.