Algorithm • medium

Sliding Window Complete Guide

Sliding window maintains a moving contiguous range while updating state incrementally.

It is the go-to strategy for substring/subarray constraints where you need best/min/max window under rules.

The key is deterministic add-right/remove-left updates so each index is touched a constant number of times.

Typical Complexity Baseline

Metric	Value
Typical traversal	`O(n)`

Video Explainer

Prefer video learning? This explainer gives a quick visual walkthrough of the core idea before you dive into the detailed sections below.

Sliding Window Technique

Channel: Profound Academy

Full video link:

https://www.youtube.com/watch?v=dOonV4byDEg

Sliding Window Visualizer

See how a moving window expands and shrinks while preserving constraints.

Sliding Window VisualizerStep 1 / 3

Expand the window to include new elements.

Input

A B C A B E B E

Window

[A B C]

Left / Right

0 / 2

Constraint

No repeated characters.

Core Concepts

Learn the core building blocks and terminology in one place before comparisons, so the mechanics are clear and duplicates are removed.

Window boundaries

What it is: Left and right pointers defining active range.

Why it matters: Window boundaries is a required building block for understanding how Sliding Window stays correct and performant on large inputs.

Add step

What it is: Include right element and update state.

Why it matters: Add step is a required building block for understanding how Sliding Window stays correct and performant on large inputs.

Shrink step

What it is: Move left boundary until constraints restore.

Why it matters: Shrink step is a required building block for understanding how Sliding Window stays correct and performant on large inputs.

State tracker

What it is: Counts/sums/sets needed for validity checks.

Why it matters: State tracker is a required building block for understanding how Sliding Window stays correct and performant on large inputs.

Best answer update

What it is: Capture optimal window length/value when valid.

Why it matters: Best answer update is a required building block for understanding how Sliding Window stays correct and performant on large inputs.

Fixed window

What it is: Window size is constant (e.g., length k).

Why it matters: Window size is constant (e.g., length k). In Sliding Window, this definition helps you reason about correctness and complexity when inputs scale.

Variable window

What it is: Window expands/shrinks based on validity condition.

Why it matters: Window expands/shrinks based on validity condition. In Sliding Window, this definition helps you reason about correctness and complexity when inputs scale.

Window validity

What it is: Constraint currently satisfied for active range.

Why it matters: Constraint currently satisfied for active range. In Sliding Window, this definition helps you reason about correctness and complexity when inputs scale.

Amortized linear

What it is: Each index enters/leaves window at most once.

Why it matters: Each index enters/leaves window at most once. In Sliding Window, this definition helps you reason about correctness and complexity when inputs scale.

Frequency map

What it is: Character/value counts used to evaluate window constraints.

Why it matters: Character/value counts used to evaluate window constraints. In Sliding Window, this definition helps you reason about correctness and complexity when inputs scale.

Putting It All Together

This walkthrough connects the core concepts of Sliding Window into one end-to-end execution flow.

Step 1

Window boundaries

Left and right pointers defining active range.

Before

window=

empty

Text: "A B C A B C B B"
left=0, right=0

→

After

window now contains unique chars
Track best length so far

Transition

Expand right to include new char

→Update counts incrementally

Why this step matters: Window boundaries is a required building block for understanding how Sliding Window stays correct and performant on large inputs.

Step 2

Add step

Include right element and update state.

Before

Duplicate detected inside window
Constraint violated

→

After

Constraint restored
Window valid again

Transition

Move left pointer right

→Remove old chars until valid

Why this step matters: Add step is a required building block for understanding how Sliding Window stays correct and performant on large inputs.

Step 3

Shrink step

Move left boundary until constraints restore.

Before

Need max sum of fixed size k
Current sum maintained

→

After

Updated sum in O(1)
No full recomputation

Transition

Add arr[right]

→Subtract arr[left-1] when window moves

Why this step matters: Shrink step is a required building block for understanding how Sliding Window stays correct and performant on large inputs.

Step 4

State tracker

Counts/sums/sets needed for validity checks.

Before

Need minimum-length window meeting target
Current total below threshold

→

After

Shortest valid window tracked
Optimal answer updated

Transition

Expand right until target met

→Then shrink left to minimize length

Why this step matters: State tracker is a required building block for understanding how Sliding Window stays correct and performant on large inputs.

How It Compares

vs Prefix sums

When to choose this: Choose sliding window when constraints depend on mutable content inside range.

Tradeoff: Prefix sums are better for static sum queries.

vs Two pointers

When to choose this: Choose sliding window for contiguous range optimization.

Tradeoff: General two pointers may be simpler for pairwise non-window problems.

vs Brute-force subarray scan

When to choose this: Choose sliding window to avoid O(n^2) range enumeration.

Tradeoff: Needs careful state update design.

Real-World Stories and Company Examples

Datadog

Monitoring alerts evaluate rolling windows over metrics streams to detect spikes and anomalies.

Takeaway: Sliding windows are practical for continuous observability workloads.

Cloudflare

Rate-limiting systems apply per-key request windows to enforce fair usage.

Takeaway: Window-based constraints protect services under burst traffic.

Spotify

Session analytics often rely on rolling windows for engagement and retention signals.

Takeaway: Window logic underpins many product analytics metrics.

Implementation Guide

Use a manual fixed-size last-seen table so the window updates are explicit without built-in map classes.

Complexity: Time O(n), Space O(min(n, alphabet))

Language

Longest unique substring with variable window

function longestUniqueWindow(text: string): number {
  const lastSeenIndexes = new Array<number>(256).fill(-1)
  let leftIndex = 0
  let bestLength = 0

  for (let rightIndex = 0; rightIndex < text.length; rightIndex += 1) {
    const charCode = text.charCodeAt(rightIndex) & 255
    const seenIndex = lastSeenIndexes[charCode]

    if (seenIndex >= leftIndex) {
      leftIndex = seenIndex + 1
    }

    lastSeenIndexes[charCode] = rightIndex
    const currentWindowLength = rightIndex - leftIndex + 1
    if (currentWindowLength > bestLength) {
      bestLength = currentWindowLength
    }
  }

  return bestLength
}

Common Problems and Failure Modes

Not shrinking enough when window invalidates.
Updating answer before ensuring validity.
Incorrectly handling repeated characters/items.
Mixing fixed and variable window logic.
Not clearing state between test cases in reusable helpers.

Tips and Tricks

Sliding window shines for contiguous subarray/substring optimization tasks.
Maintain incremental state; never recompute full window from scratch.
Shrink window only while constraint is violated, then resume expansion.
Use frequency maps and distinct counters together for tight complexity bounds.

When to Use

Use these signals to decide if this data structure/algorithm is the right fit before implementation.

Real-system usage signals

Transforms repeated subarray recomputation into linear-time updates.
Natural fit for real-time stream monitoring and threshold checks.
Works well with hash maps and frequency counters for text/data windows.

LeetCode-specific tips (including pattern-identification signals)

Identification signal: prompt asks for longest/shortest contiguous segment meeting a constraint.
Identification signal: recomputing each window from scratch is too slow, but add/remove updates are possible.
Words like "at most k", "contains all", or "without repeating" often map directly to sliding-window templates.
For Sliding Window questions, start by naming the core invariant before writing code.
Use the constraint section to set time/space target first, then pick the data structure/algorithm.
Solve one tiny example by hand and map each transition to your variables before implementing.
Run adversarial cases: empty input, duplicates, max-size input, and sorted/reverse patterns when relevant.
During interviews, explain why your approach is the right pattern for this prompt, not just why the code works.

LeetCode Progression (Easy to Hard)

Back to DSA Guide Catalog

#	Problem	Difficulty	Typical Complexity
1	Maximum Average Subarray I	Easy	`O(n)`
2	Minimum Size Subarray Sum	Medium	`O(n)`
3	Longest Substring Without Repeating Characters	Medium	`O(n)`
4	Permutation in String	Medium	`O(n)`
5	Find All Anagrams in a String	Medium	`O(n)`
6	Longest Repeating Character Replacement	Medium	`O(n)`
7	Subarray Product Less Than K	Medium	`O(n)`
8	Minimum Window Substring	Hard	`O(n)`
9	Sliding Window Maximum	Hard	`O(n)`
10	Substring with Concatenation of All Words	Hard	`O(n*k)`