Sliding Window Pattern: Two Variants, One Invariant

Treating the sliding window pattern as a single technique is the first mistake. You see "contiguous subarray" in a problem, you reach for a window, and you figure out the rest as you go. That's where the bugs start. The sliding window isn't one technique, it's two distinct variants with different invariants, different pointer mechanics, and different identification triggers. Mix them up and problems that should take 15 minutes take 45.

What the sliding window pattern solves

The sliding window pattern avoids recomputing an entire subarray from scratch at every position. Instead of recalculating, it maintains a running result by adding the new element entering the window and removing the element leaving it. That drops O(n*k) brute force to O(n) for any problem involving contiguous subarrays or substrings.

A concrete example makes this redundancy obvious.

Consider a brute force approach to finding the maximum sum of any 4 consecutive elements in an array. You'd compute the sum for positions 0-3, then 1-4, then 2-5, each time adding all 4 elements from scratch. For an array of length n and window size k, that's O(n*k) work because moving from one position to the next, 3 of the 4 elements are identical. You're readding values you already summed.

The sliding window eliminates that redundancy. When the window slides one position right, you add the new element entering and subtract the element leaving. One addition and one subtraction, regardless of window size, and the running total stays correct because you're maintaining an incremental invariant where the current result always reflects exactly the elements inside the window.

This idea goes further than you'd expect. Kadane's algorithm for maximum subarray sum is a specialized variable sliding window. The "window" grows when extending the subarray increases the sum and resets when it doesn't. Once you see sliding window as an incremental invariant, Kadane's logic clicks differently, even though textbooks rarely frame it that way.

Fixed sliding window: One size, one invariant

A fixed sliding window has a window size defined by the problem. Both pointers advance together, one step at a time, after the initial window is filled. The invariant is that exactly k elements are inside the window at every step after initialization.

Walk through "find the maximum sum of any k=4 consecutive elements" with array [2, 1, 5, 1, 3, 2]:

Trace through the state at each step:

• Initial window [2, 1, 5, 1]: sum = 9, max = 9
• Slide right to index 4: add 3, remove 2 -> sum = 10, max = 10
• Slide right to index 5: add 2, remove 1 -> sum = 11, max = 11

Two things stand out. The window size never changes after the initial fill, because every step adds one element and removes one. And the time complexity is O(n) regardless of k, because each element enters the window exactly once and leaves exactly once.

The fixed variant is the simpler of the two. If the problem specifies an exact window size, you're almost certainly looking at a fixed sliding window, and the approach is always the same: fill the window, slide it, track the result.

Variable sliding window: Expand, check, shrink

A variable sliding window doesn't have a predefined size. Instead of both pointers advancing together, the right pointer expands the window until some condition breaks and the left pointer shrinks it until the condition is restored. After each shrink phase, the window always satisfies the problem's constraint.

It feels different from the fixed variant because the two pointers move independently. Right advances on every iteration, but left only moves when the window violates the condition.

Take "find the length of the longest substring with at most K=2 distinct characters" on string "eceba":

Trace the variable state:

right=0 (e): count={e:1}, distinct=1, window="e", length=1 right=1 (c): count={e:1,c:1}, distinct=2, window="ec", length=2

• right=2 (e): count={e:2,c:1}, distinct=2, window="ece", length=3
• right=3 (b): count={e:2,c:1,b:1}, distinct=3 > k=2
  • shrink: remove e -> count={e:1,c:1,b:1}, still 3
  • shrink: remove c -> count={e:1,b:1}, distinct=2, window="eb", length=2
• right=4 (a): count={e:1,b:1,a:1}, distinct=3 > k=2
  • shrink: remove e -> count={b:1,a:1}, distinct=2, window="ba", length=2
• Result: 3 (substring "ece")

The hash map is doing the heavy lifting here. Variable sliding window problems on strings almost always need a frequency map (a hash table pattern) to track what's inside the window. It's what makes the condition check O(1). Without it, you'd scan the entire window to evaluate the constraint every time, and the time advantage disappears.

The time complexity is still O(n) even though the inner while loop exists. Each element enters the window at most once when the right pointer advances and leaves at most once when the left pointer advances, so the total pointer movement across the entire algorithm is at most 2n.

How to identify the right sliding window pattern

You can usually tell which variant you need from the problem statement alone, before writing any code.

Fixed sliding window triggers

Variable sliding window triggers

Once you can read a problem and classify it as fixed or variable in 30 seconds, the implementation follows directly. You don't need to invent the solution structure from scratch each time, because the variant tells you what to build.

Common mistakes and why they happen

Four bugs show up over and over in sliding window implementations, and they're all avoidable once you know what to watch for.

One of fifteen pattern families

The sliding window is one of 15 pattern families across Codeintuition's learning path that cover the majority of coding interview problems. For the full taxonomy and how they connect, see the patterns guide. If you want to see how this same recognition approach works for a completely different pattern family, the DP identification framework applies the same reasoning to dynamic programming.

Codeintuition's Arrays course covers both variants, including the identification lesson that teaches the structural triggers for variable sliding window. The course has 8 patterns total, with 37 problems sequenced from fundamentals through hard. Variable sliding window alone has 4 problems that build on each other, each adding a new wrinkle to the expand, check, shrink cycle.

You can start with the free tier and work through both variants before deciding whether to continue.

Next time you hit a "longest substring" problem, you won't be guessing at the expand and shrink logic. You'll read "contiguous range" and "at most K" and know the variant before you've finished the problem statement. One invariant, applied two ways, and you can trace the pointer state in your head before you type anything.