Sliding window

coreCommon atGoogleAmazonMetaAnthropicRead firstTwo pointersHash mapsPractise in the Sandbox →

A sliding window keeps a contiguous range [left..right] plus a small summary of what’s inside it (a sum, a count, a set). Move right to grow it. When it breaks the rule, move left to shrink it. Each element enters once and leaves once, so the scan is O(n).

The idea in plain words

Picture a train window as the train passes a row of houses. You never re-look at every house you can see. One house slides in on the right, one slides out on the left, and you update what you know.

The brute-force way re-examines every possible range: for each start, walk every end. That’s O(n²) ranges, and often more work per range on top. A window reuses the previous answer:

• Adding an element on the right updates the summary in O(1). Add to the sum, bump a count.
• Removing one on the left undoes that in O(1). Subtract, decrement.

If both are cheap, you never recompute from scratch.

See it

Type your own numbers and limit, then step through. Watch L only ever move right. That one-way movement is why it’s linear.

Grow right, shrink left

step through

values (≥ 0)limit

L

2

1

3

1

1

4

2

1

01234567

sum0

best0

window∅

best_at–

valid windowwindow breaks the rule

Start with an empty window. Goal: the longest stretch whose sum stays ≤ 6.

↺◀▶ Play▶1 / 20

When to reach for it

The problem says…	Why a window fits
“longest / shortest contiguous subarray or substring such that…”	Contiguous ranges are exactly what a window represents.
“every block of k consecutive…” / “in the last k seconds”	Fixed-size window: slide it one step at a time.
“at most k distinct / repeated / zeros…”	The rule is checkable from a count map you can update incrementally.
a stream of events with a time horizon	The window is a queue of “still relevant” items; old ones fall off the left.

The monotonic requirement

A variable window only works if growing can only make the window “worse” and shrinking can only make it “better” (or the reverse). Sums of non-negative numbers have this property. Sums with negative numbers don’t: dropping a negative from the left makes the sum bigger. Then you need prefix sums with a hash map instead.

How it works

There are two shapes. Learn them as templates.

Fixed size k

1. Build the first window [0..k-1] and its summary.
2. For each new index r from k onward: add xs[r] and remove xs[r-k].
3. After each slide, compare the window’s summary to the best so far.

Python

max_window_sum.py

def max_window_sum(xs: list[int], k: int) -> int:
    """Largest sum of any k consecutive values. O(n) time, O(1) space."""
    if not 1 <= k <= len(xs):
        raise ValueError("need 1 <= k <= len(xs)")
    window = sum(xs[:k])            # first window, paid once
    best = window
    for r in range(k, len(xs)):
        window += xs[r] - xs[r - k]  # slide: add the new right, drop the old left
        best = max(best, window)
    return best


if __name__ == "__main__":
    assert max_window_sum([4, 2, 1, 7, 8, 1, 2, 8, 1, 0], 3) == 16  # 1+7+8
    assert max_window_sum([5], 1) == 5
    print("ok")

TypeScript

max_window_sum.ts

import assert from "node:assert/strict";

/** Largest sum of any k consecutive values. O(n) time, O(1) space. */
export function maxWindowSum(xs: number[], k: number): number {
  if (k < 1 || k > xs.length) throw new RangeError("need 1 <= k <= xs.length");
  let window = 0;
  for (let i = 0; i < k; i++) window += xs[i]; // first window, paid once
  let best = window;
  for (let r = k; r < xs.length; r++) {
    window += xs[r] - xs[r - k]; // slide: add the new right, drop the old left
    best = Math.max(best, window);
  }
  return best;
}

assert.equal(maxWindowSum([4, 2, 1, 7, 8, 1, 2, 8, 1, 0], 3), 16); // 1+7+8
assert.equal(maxWindowSum([5], 1), 5);
console.log("ok");

C#

max_window_sum.cs

// Largest sum of any k consecutive values. O(n) time, O(1) space.
static long MaxWindowSum(int[] xs, int k)
{
    if (k < 1 || k > xs.Length) throw new ArgumentOutOfRangeException(nameof(k));
    long window = 0;
    for (int i = 0; i < k; i++) window += xs[i]; // first window, paid once
    long best = window;
    for (int r = k; r < xs.Length; r++)
    {
        window += xs[r] - xs[r - k]; // slide: add the new right, drop the old left
        best = Math.Max(best, window);
    }
    return best;
}

if (MaxWindowSum([4, 2, 1, 7, 8, 1, 2, 8, 1, 0], 3) != 16) throw new Exception("expected 16");
if (MaxWindowSum([5], 1) != 5) throw new Exception("expected 5");
Console.WriteLine("ok");

Variable size (“grow, then shrink while invalid”)

1. Move right forward one step and add xs[right] to the summary.
2. While the window breaks the rule, remove xs[left] and move left forward.
3. Now the window is valid. Record its length or contents if it’s the best so far.

Python

longest_within.py

def longest_within(xs: list[int], limit: int) -> int:
    """Length of the longest contiguous run with sum <= limit. Values must be >= 0."""
    best = 0
    left = 0
    total = 0
    for right, x in enumerate(xs):
        total += x                      # 1. grow: include xs[right]
        while total > limit:            # 2. shrink until the rule holds again
            total -= xs[left]
            left += 1
        best = max(best, right - left + 1)  # 3. window [left..right] is valid: record it
    return best


if __name__ == "__main__":
    assert longest_within([2, 1, 3, 1, 1, 4, 2, 1], 6) == 4  # [1, 3, 1, 1]
    assert longest_within([], 5) == 0
    assert longest_within([9, 9], 5) == 0
    print("ok")

TypeScript

longest_within.ts

import assert from "node:assert/strict";

/** Length of the longest contiguous run with sum <= limit. Values must be >= 0. */
export function longestWithin(xs: number[], limit: number): number {
  let best = 0;
  let left = 0;
  let total = 0;
  for (let right = 0; right < xs.length; right++) {
    total += xs[right]; // 1. grow: include xs[right]
    while (total > limit) { // 2. shrink until the rule holds again
      total -= xs[left];
      left++;
    }
    best = Math.max(best, right - left + 1); // 3. window [left..right] is valid: record it
  }
  return best;
}

assert.equal(longestWithin([2, 1, 3, 1, 1, 4, 2, 1], 6), 4); // [1, 3, 1, 1]
assert.equal(longestWithin([], 5), 0);
assert.equal(longestWithin([9, 9], 5), 0);
console.log("ok");

C#

longest_within.cs

// Length of the longest contiguous run with sum <= limit. Values must be >= 0.
static int LongestWithin(int[] xs, int limit)
{
    int best = 0, left = 0;
    long total = 0;
    for (int right = 0; right < xs.Length; right++)
    {
        total += xs[right];                 // 1. grow: include xs[right]
        while (total > limit)               // 2. shrink until the rule holds again
        {
            total -= xs[left];
            left++;
        }
        best = Math.Max(best, right - left + 1); // 3. window [left..right] is valid: record it
    }
    return best;
}

if (LongestWithin([2, 1, 3, 1, 1, 4, 2, 1], 6) != 4) throw new Exception("expected 4");
if (LongestWithin([], 5) != 0) throw new Exception("expected 0");
if (LongestWithin([9, 9], 5) != 0) throw new Exception("expected 0");
Console.WriteLine("ok");

Longest vs shortest

For longest valid, record the answer after shrinking, once the window is valid. For shortest valid (“smallest window whose sum ≥ target”), shrink while it is still valid and record inside the loop, before each removal. Mixing these up is the most common window bug.

What it costs

	Time	Extra space
Brute force (all ranges)	O(n²), or O(n·k) for fixed size	O(1)
Sliding window, numeric summary	O(n): each index enters once, leaves once	O(1)
Sliding window, count map over an alphabet of size σ	O(n)	O(σ)

The while loop inside the for loop looks like O(n²), but it isn’t. Count how many times left++ can run in total across the whole scan: at most n. That style of argument is called amortized analysis. Interviewers like to hear you make it.

Additions needed: brute force vs sliding window

drag the sliders

n = 20k = 5

Re-sum each window

80

Slide (add 1, drop 1)

35

Brute force does about (n − k + 1) · k additions; sliding does about 2n. Set k ≈ n/2 to see the gap at its widest.

Variations you’ll meet

• Count-map window. The summary is a hash map from item to count, plus a counter for “how many keys satisfy the rule”. You check the rule in O(1) instead of scanning the map each step.
• Time-based window. Instead of index distance, evict while now - oldest.timestamp >= horizon. Use a deque (or a ring buffer) of timestamps.
• Window with max/min. A plain sum can’t tell you the max inside the window. Pair the window with a monotonic deque to get O(1) max per step.
• “Exactly k” = “at most k” − “at most k−1”. Exact-count conditions usually aren’t monotonic. Two at-most windows are.

Pitfalls

• Negative numbers break the variable-window logic (see the caution above).
• Off-by-one in length. [left..right] has right - left + 1 elements.
• Empty input / k > n. Decide up front whether to return 0, throw, or return nothing. Say it out loud.
• Forgetting to undo state on shrink. If you add to a map on grow, decrement on shrink, and delete keys that hit zero if you use len(map) as “distinct count”.
• Using if instead of while to shrink. One step left may not be enough to restore the rule.

In the interview

• Confirm the range is contiguous. If it isn’t (a subsequence), a window is the wrong tool.
• Ask whether values can be negative, and whether the input is a stream.
• Say the invariant out loud: “Between iterations, [left..right] is always valid and total is its sum.”
• State the complexity with the amortized argument, not just “it’s O(n)”.

Check yourself

Check yourself

pick one

You need the longest subarray with sum ≤ 10, but the array can contain negative numbers. Is the grow/shrink window still correct?

AYes, the logic does not depend on the valuesBNo: removing a negative from the left increases the sum, so shrinking no longer always helpsCOnly if you sort the array first

Check yourself

pick one

In the variable-size template, the inner while loop can run many times for one step of right. What is the total time over the whole scan?

AO(n²)BO(n log n)CO(n)DO(n·k)

Practice on your own

These are classic textbook exercises, not gym questions:

• Maximum average of any k consecutive readings.
• Smallest subarray with sum ≥ target (non-negative values).
• Longest stretch of a binary array with at most k zeros flipped to ones.
• Count subarrays whose product is less than k (positive values).

Go deeper

• Competitive Programmer’s Handbook (Laaksonen), ch. 8, “Amortized analysis”: two pointers and sliding window.
• cp-algorithms: minimum stack / minimum queue, the trick behind O(1) window max/min.
• MIT 6.006 lecture notes on amortization, for the “inner loop is still linear” argument.

Related

Two pointersThe parent pattern: two indices that only move forward.

Prefix sumsRange sums when the window rule isn't monotonic.

Monotonic stack / queueMax or min of every window in O(n).

Queues and dequesTime-based windows over a stream.