Why is the sliding window O(n) instead of O(n·k)?

The naive approach recomputes each window's sum by adding up its k elements, which costs O(k) per window and O(n·k) overall. The sliding window observes that adjacent windows overlap in k-1 elements, so it updates the sum with just two operations — one subtraction and one addition — per slide. That is O(1) per step and O(n) total.

What is the difference between a fixed and a variable sliding window?

A fixed-size window always spans exactly k elements and slides one step at a time — used for problems like maximum sum of k consecutive numbers. A variable-size window grows and shrinks based on a condition (two pointers, left and right), used for problems like the longest substring without repeating characters or the smallest subarray with a sum at least S.

When can you use the sliding window technique?

It applies when you need something about contiguous subarrays or substrings and the quantity you track can be updated incrementally as the window moves — sums, counts, character frequencies, or a running max/min via a deque. If a window's answer can be derived cheaply from the previous window, sliding beats recomputing.

What is the sliding window used for?

Maximum or minimum sum of k consecutive elements, longest substring without repeating characters, smallest subarray with a given sum, moving averages in signal processing, rate limiting over a time window, and streaming statistics where only a recent window of data matters.

ALGORITHMS · 16 / SLIDING WINDOW

The Moving Frame.

Q: What is the sliding window technique?

The sliding window technique processes all contiguous windows of an array efficiently by reusing work between adjacent windows. For a fixed size k, instead of re-summing every window from scratch, you keep a running sum: when the window slides one step, you subtract the element that just left and add the element that just entered. This turns an O(n·k) brute force into a single O(n) pass.

Which three neighbours add up highest? The lazy way re-adds every window from scratch. The smart way keeps a running total and, as the frame slides, just subtracts what left and adds what entered — the whole array in one O(n) pass.

THE GIST · 20 SECONDS

The sliding window answers "best contiguous run of k" without redoing work. Sum the first k elements once. Then slide: each step, subtract the element leaving the window and add the one entering — the sum updates in O(1). Track the best as you go. Adjacent windows overlap in k−1 elements, so re-summing them is pure waste.

Windowk consecutive cells
Enter+ the new right element
Leave− the old left element
O(n)one pass, not n×k

Hit Step to slide the frame one cell — or Play and watch it glide across, keeping the best sum without re-adding a thing.

UNDER THE HOOD

What you just played, written down

The trick is noticing what stays the same. Two neighbouring windows share all but two elements — so throw away one, take in one, and never re-add the middle.

How the sliding window thinks — four moves

Sum the first window once. Add elements 0 … k−1. That is your starting window sum and your first best.
Slide by one. The window moves right: element i−k falls out of the left, element i enters on the right.
Update in O(1). sum += arr[i] − arr[i−k]. No loop — one add, one subtract, whatever k is.
Track the best. After each slide, if sum > best, remember it. When the window reaches the end, best is your answer.

WHY BRUTE FORCE WASTES SO MUCH

Re-summing each window adds up all k elements every time — and adjacent windows overlap in k − 1 of them. You re-add the same middle numbers over and over. The window just remembers the total instead.

The whole thing in code

def max_sum(arr, k):
    if len(arr) < k:
        return None
    # sum the first window once
    window = sum(arr[:k])
    best = window
    # slide: drop the left, add the right
    for i in range(k, len(arr)):
        window += arr[i] - arr[i - k]
        if window > best:
            best = window
    return best

TIMEO(n)vs O(n·k) naive

SPACEO(1)just the running sum

FIXED VS VARIABLE WINDOWS

This is a fixed window — always k wide. A variable window uses two pointers that grow and shrink on a condition, for "longest substring without repeats" or "smallest subarray summing to ≥ S."

⚠ Max in a window is trickier

A running sum updates in O(1), but a running maximum can't — removing the leaving element might remove the max. The sliding-window maximum keeps a monotonic deque to still hit O(n).

↔ Two pointers

The sliding window is a special two-pointer pattern where left and right bound a range. Variable windows move them independently; fixed windows keep them a constant k apart.

★ Where it's used

Moving averages, longest-substring problems, smallest-subarray-with-sum, rate limiting over a time window, and streaming stats over recent data.

SOLVE IT YOURSELF

Solve it: max sum of k consecutive

This one is yours to write — in Python or TypeScript, running for real in your browser. Keep a running sum and slide it. Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are below and Reveal solution is one click away.

YOUR TASK

Implement max_sum(arr, k): return the maximum sum of any k consecutive elements of arr. Use a sliding window so the whole thing runs in O(n). If the array is shorter than k, return None.

HINTS — 4 IDEAS

Sum the first k elements once; call it window, and set best = window.
For i from k to the end: window += arr[i] - arr[i-k] — add the entering, subtract the leaving.
After each slide, update best = max(best, window).
Never re-loop over the window — that's what makes it O(n) instead of O(n·k).

CPython · WebAssembly

QUICK CHECK

Did it stick?

FAQ

Sliding window, answered

What is the sliding window technique?

A way to process every contiguous window of an array efficiently by reusing overlap. For a fixed size k, keep a running sum and, on each slide, subtract the leaving element and add the entering one — turning O(n·k) into O(n).

Why is it O(n)?

Adjacent windows share k−1 elements, so each slide is just one subtraction and one addition — O(1) — done n−k times. Total O(n), versus re-summing each window at O(n·k).

Fixed vs variable window?

Fixed: always k wide, slides one step (max sum of k). Variable: two pointers grow/shrink on a condition (longest substring without repeats, smallest subarray with sum ≥ S).

When can I use it?

When you need something about contiguous subarrays and the tracked quantity — a sum, count, or frequency — can be updated incrementally as the window moves.

Where is it used?

Moving averages, longest/smallest subarray problems, character-frequency substring problems, rate limiting over a time window, and streaming statistics.

Finished this one? 0 / 17 Algorithms done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA

The Moving Frame.

What you just played, written down

How the sliding window thinks — four moves

The whole thing in code

⚠ Max in a window is trickier

↔ Two pointers

★ Where it's used

Solve it: max sum of k consecutive

Did it stick?

Sliding window, answered

Explore the topic

More Algorithms

Explore more from Vibe Engines

What you just played, written down

How the sliding window thinks — four moves

The whole thing in code

⚠ Max in a window is trickier

↔ Two pointers

★ Where it's used

Solve it: max sum of k consecutive

Did it stick?

Sliding window, answered

Explore the topic

More Algorithms

Explore more from Vibe Engines

Get the next one in your inbox.