02. Sliding Window

TL;DR

Maintain a contiguous segment of an array or string and update aggregate statistics as the right edge expands and the left edge optionally contracts—either for a fixed width or until constraints are restored. Variable windows formalize "longest valid" or "shortest covering" subarrays in linear time when validity is monotone as the right edge grows.

Core Basics

• Object: a contiguous range ([L, R]) with aggregate state (counts, sum, uniqueness bitset) updated in amortized (O(1)) per boundary move.
• Fixed vs variable: fixed width = single pass; variable needs a monotone validity rule so shrinking (L) restores feasibility.
• Staff-level bar: state whether you optimize “longest valid” vs “shortest covering” and which edge is greedy per step.

Recognition Cues

• Phrases: "longest substring …", "minimum size subarray …", "at most K distinct", "permutation of …", "consecutive", "window of length k".
• Shapes: linear sequence; constraint on counts, uniqueness, or coverage; optimization over all subarrays or substrings.
• When the answer is about exactly K of something and "at most K" is easier, look for inclusion–exclusion between two window counts.

Use-case Lens

• Best when: the answer is a contiguous subarray/substring and you can update the window state by adding the right element and removing the left element.
• Not for: non-contiguous subsequences, arbitrary subsets, or constraints where removing from the left does not make progress toward validity.
• Main invariant: every index enters the window once and leaves at most once, so the nested-looking shrink loop is still amortized (O(n)).
• Interview move: explain which of the four window families you are solving before writing code: fixed size, longest valid, count windows, or shortest covering.

Diagram

Four Sliding Window Families

Sliding window is a set of templates, not one memorized algorithm. Use this table before coding:

Walkthrough: constant window max sum

For values = [2, 1, 5, 1, 3, 2], k = 3:

Do not recompute the sum for each window. Carry state forward by subtracting the outgoing value and adding the incoming value.

Walkthrough: longest valid window

For “longest substring without repeating characters”, the window state is a frequency map or set. Grow right; when the new character creates a duplicate, move left and remove characters until the window is valid again. Only then update best.

Step-by-step Visual: Longest Substring Without Repeating

Problem: find the length of the longest substring without repeating characters.

Input: s = "abcabcbb"

The window is always s[left..right]. The right pointer adds a character. If that makes the window invalid, the left pointer removes characters until the window is valid again.

Color legend

Window anatomy

Stage 1: expand while the window is valid

Read this stage:

• right has expanded from index 0 to index 2.
• The highlighted green window is abc.
• seen = {a,b,c}, so every character appears once.
• The invariant is satisfied: no duplicate inside the window.
• Update best = max(best, window length) = 3.

Stage 2: expand right and detect the duplicate

Read this stage:

• right moves to index 3 and adds another a.
• The red highlighted window is abca.
• It is red because a appears twice.
• The invariant is broken, so do not update best.
• Next move: keep right fixed and move left until the old a leaves the window.

Stage 3: shrink left only until valid again

Read this stage:

• left moves from index 0 to index 1.
• The old a at index 0 becomes gray because it is removed.
• The green window is now bca.
• The duplicate is gone, so the invariant is restored.
• best stays 3 because the current valid window length is also 3.

Important: do not reset the whole window. Keep bca; it may still be part of the best future answer.

Stage 4: repeat the same idea

Read this stage:

• Starting valid window before expansion was bca.
• right moves to index 4 and adds b, so the temporary window becomes bcab.
• bcab is invalid because b appears twice.
• Move left once to remove the old b.
• New valid window becomes cab, with left = 2, right = 4, and best = 3.

Key idea: the algorithm does not restart after a duplicate. It keeps the useful part of the window and only moves left enough to restore the invariant. That is why the solution is linear.

Step-by-step Visual: Minimum Size Subarray Sum

Problem: find the shortest contiguous subarray with sum at least target.

Input: target = 7, values = [2, 3, 1, 2, 4, 3]

This is the opposite update timing from “longest valid”: first expand until the window becomes valid, then shrink while it stays valid so the answer becomes as short as possible.

Rule for this problem:

• Expand while sum < target.
• When sum >= target, the window is valid.
• Record the length immediately.
• Then shrink from the left while the window stays valid, because every shrink may produce a shorter answer.

Stage 1: expand until sum reaches the target

Read this stage:

• We keep moving right because the sum is below 7.
• After adding index 3, the window is [2,3,1,2].
• Sum is 8, so the window finally becomes valid.
• Record candidate length 4.
• Next move: shrink from the left to see if a shorter valid window exists.

Stage 2: shrink and lose validity

Read this stage:

• Remove the leftmost value 2.
• The window becomes [3,1,2].
• Sum drops from 8 to 6.
• The window is red because it is no longer valid.
• Stop shrinking. Expanding right is now the only move that can restore validity.

Stage 3: expand again, then shrink multiple times

Read this stage:

• Add 4, making [3,1,2,4] with sum 10.
• Since the window is valid, record length 4.
• Shrink once: remove 3, window becomes [1,2,4], sum is 7, still valid, so update best = 3.
• Shrink again: remove 1, window becomes [2,4], sum is 6, invalid.
• Stop shrinking and expand again.

Stage 4: final shortest window

Read this stage:

• Add 3, making [2,4,3] with sum 9.
• Shrink once: remove 2, leaving [4,3] with sum 7.
• [4,3] is still valid and has length 2, so update best = 2.
• Removing 4 would make the sum invalid, so stop.
• Final answer is 2.

Mental model: for shortest windows, update the answer inside the shrink loop, because every successful shrink may discover a smaller valid segment.

Understanding

A window is a interval on a timeline: right extends commitment; left releases old commitments when the window becomes invalid (too heavy, too many types) or when searching for the shortest valid segment (shrink while still valid). Fixed-size windows slide by advancing both edges together—state is a snapshot of the last windowSize elements.

Generic Recipe

1. Clarify fixed vs variable window and whether you need longest, shortest, or count of windows.
2. Initialize left = 0, empty aggregates (counts, multiset, "need" vs "have" for coverage).
3. Grow right from 0 to n-1: ingest sequence[right] into state.
4. For variable invalidating: while invalid and left <= right, eject sequence[left], increment left.
5. For shortest valid: after fixing validity at right, shrink while valid to tighten left.
6. For fixed size: when right - left + 1 == windowSize, record answer then eject sequence[left] and advance left.
7. For exactly K distinct: compute atMost(k) - atMost(k - 1) on the same machinery.

Complexity

• Time: typically (O(n)) for each pass over the sequence when each element enters and leaves the window at most once; multiset-heavy variants may add log factors if tree-backed structures are used.
• Space: (O(k)) or (O(\text{alphabet})) for frequency maps; deque-based max-window uses (O(\text{windowSize})).

Memory Hooks

• Operational mantra: expand right to include new evidence, then move left only when the chosen window family says to.
• Anti-panic: name the family first: fixed size, longest valid, count windows, or shortest covering. Then decide when left moves.

Study Pattern (SDE3+)

• Recognition drill (10 min): tag prompts by window family and whether validity is monotone enough for amortized linear time.
• Implementation sprint (25 min): code one longest-valid and one shortest-covering window; update answer at the correct loop point.
• Staff follow-up (10 min): explain how the design changes for streams, Unicode alphabets, or exact-K constraints.

Generic Code Template

Go

package main

// Variable window: longest length with at most maxDistinct distinct values (counts as map).
func longestAtMostDistinct(values []int, maxDistinct int) int {
	if maxDistinct < 0 {
		return 0
	}
	frequency := make(map[int]int)
	left := 0
	best := 0
	for right := range values {
		frequency[values[right]]++
		for len(frequency) > maxDistinct {
			leftValue := values[left]
			frequency[leftValue]--
			if frequency[leftValue] == 0 {
				delete(frequency, leftValue)
			}
			left++
		}
		currentLen := right - left + 1
		if currentLen > best {
			best = currentLen
		}
	}
	return best
}

// Fixed window: slide length windowSize; sums example slice (replace with your statistic).
func fixedWindowMaxSum(values []int, windowSize int) int {
	if windowSize <= 0 || len(values) < windowSize {
		return 0
	}
	windowSum := 0
	for index := 0; index < windowSize; index++ {
		windowSum += values[index]
	}
	best := windowSum
	for nextIndex := windowSize; nextIndex < len(values); nextIndex++ {
		outgoing := values[nextIndex-windowSize]
		incoming := values[nextIndex]
		windowSum += incoming - outgoing
		if windowSum > best {
			best = windowSum
		}
	}
	return best
}

func main() {}

JavaScript

// Variable window: minimum length subarray with sum at least target (positive numbers typical).
function minSubArrayLen(target, values) {
  let left = 0;
  let windowSum = 0;
  let best = Infinity;
  for (let right = 0; right < values.length; right += 1) {
    windowSum += values[right];
    while (windowSum >= target && left <= right) {
      const length = right - left + 1;
      if (length < best) {
        best = length;
      }
      windowSum -= values[left];
      left += 1;
    }
  }
  return best === Infinity ? 0 : best;
}

// Exactly K distinct via atMost(k) - atMost(k-1) pattern (sketch: call twice).
function countSubarraysExactlyKDistinct(values, targetDistinct) {
  const atMost = (limit) => {
    const frequency = new Map();
    let left = 0;
    let count = 0;
    for (let right = 0; right < values.length; right += 1) {
      const rightValue = values[right];
      frequency.set(rightValue, (frequency.get(rightValue) ?? 0) + 1);
      while (frequency.size > limit) {
        const leftValue = values[left];
        frequency.set(leftValue, frequency.get(leftValue) - 1);
        if (frequency.get(leftValue) === 0) {
          frequency.delete(leftValue);
        }
        left += 1;
      }
      count += right - left + 1;
    }
    return count;
  };
  return atMost(targetDistinct) - atMost(targetDistinct - 1);
}

Variants

• Fixed-size — permutation in string, anagrams, sliding window maximum (often monotonic deque).
• Variable invalidating — longest without repeat (set), longest with replacement budget (counts), minimum covering substring (need/have maps).
• atMost(K) − atMost(K−1) — subarrays with exactly K distinct integers; transforms exact constraint into two monotone counts.
• Shrink-when-valid — shortest subarray with sum ≥ S after expanding until valid.

Representative Problems

• 003. Longest Substring Without Repeating Characters — variable window with uniqueness
• 567. Permutation in String — fixed window with frequency match
• 992. Subarrays with K Different Integers — exactly K via two atMost passes
• 209. Minimum Size Subarray Sum — shortest window meeting threshold
• 076. Minimum Window Substring — need/have coverage with variable window

Anti-patterns

• Advancing left without ejecting state—stale counts break validity.
• Using exactly K directly when at most K monotone counting simplifies the logic.
• Assuming (O(n)) when each right triggers an inner loop that scans arbitrarily far with non-monotone validity (verify each index leaves the window a bounded number of times).
• Confusing longest vs shortest window update timing (update inside shrink loop vs after).