Sliding Window: From Brute Force to Linear Time

Sliding window is what you reach for the moment a problem mentions a contiguous subarray or substring and asks for a best, longest, shortest, or count. It is the difference between an O of n squared solution that times out and a clean O of n one that does not.

The insight is almost embarrassingly simple: when you slide a window forward by one element, you do not need to recompute everything inside it. You add the element entering on the right and remove the one leaving on the left. The work per step is constant, so the whole pass is linear.

From brute force to a window

The naive approach to maximum-sum subarray of size k recomputes the sum of every window from scratch. That is k work, n times, which is O of n times k. Wasteful.

The windowed version keeps a running sum. Each step you add the incoming value and subtract the outgoing one. One addition, one subtraction, done. You just turned nested loops into a single sweep.

Fixed vs variable windows

There are two kinds, and knowing which you are in saves real time:

• Fixed window. The size is given (longest subarray of exactly k elements). Both ends move together in lockstep. Bookkeeping is minimal.
• Variable window. The size depends on a condition (longest substring with no repeating characters, smallest subarray summing to at least a target). The right edge expands greedily; the left edge contracts only when a constraint breaks.

Most interview pain lives in the variable case, so let us make it concrete.

The variable window loop

The shape is always the same:

• Expand right one step and update your window state.
• While the window is invalid, shrink from left and update state.
• After each step, record the answer if the current window beats your best.

Notice each pointer only ever moves forward. Even though there is a nested while loop, left advances at most n times total across the entire run. That amortized accounting is why the whole thing stays linear despite looking like it might be quadratic.

Picking the right window state

The state you carry is the real design decision:

• A running sum or count for numeric constraints.
• A frequency map for character or value constraints.
• A set when you only care about presence, like detecting a repeat.

Keep the state cheap to update in both directions. If adding or removing an element costs more than constant or near-constant time, you lose the linear guarantee.

Where it shows up beyond toy problems

This is not just interview trivia. Rate limiting, for example, is a sliding window over timestamps: you count requests inside a moving time range and reject when the window gets too full. Our rate limiter challenge makes that connection explicit, and it is a great bridge from algorithm drills to systems thinking. If that sparks interest, the System Design track goes deeper.

Drill it deliberately

Work the fixed case until it is boring, then live in the variable case where the real learning is. The Algorithms lessons walk through each window-state choice, and a guided roadmap keeps you progressing instead of cherry-picking.

Sliding window rewards reps. Once the expand-then-contract rhythm is in your fingers, a whole category of problems stops being scary. Want to prove it under a clock? Jump into the arena and see if you can still beat the machine.