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.

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.

Diagram

Pattern control flow (customize nodes for this pattern). camelCase node IDs.

Mental Model

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})).

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).