Coding

Sliding Window

A computational technique that converts nested loops into a single loop by maintaining a 'window' of elements that slides across a linear data structure (array or string).

Cheat Sheet

Prime Use Case

Use when asked to find a contiguous subarray or substring that satisfies a specific constraint (e.g., sum, length, or character count).

Critical Tradeoffs

  • Reduces time complexity from O(N²) or O(N³) to O(N).
  • Requires O(1) or O(K) auxiliary space to track window state.
  • Only applicable to contiguous sequences; fails on non-contiguous subsets.

Killer Senior Insight

Sliding Window is essentially 'State Memoization' for contiguous ranges; instead of recomputing the entire range, you incrementally update the state by adding the 'entering' element and removing the 'exiting' element.

Recognition

Common Interview Phrases

Find the longest/shortest subarray/substring with property X.
Find the maximum sum of K consecutive elements.
Given a string, find the smallest window containing all characters of another string.
Constraints like N > 10^5, suggesting an O(N) or O(N log N) solution is required.

Common Scenarios

  • Fixed-size window: Finding the average of all subarrays of size K.
  • Dynamic-size window: Longest substring with at most K distinct characters.
  • Shrinkable window: Smallest subarray with a sum greater than or equal to S.
  • String permutation matching (e.g., find all anagrams of P in S).

Anti-patterns to Avoid

  • Attempting to use it on non-contiguous subsequences (use Dynamic Programming or Subsets instead).
  • Using it on arrays with negative numbers when looking for a target sum (Prefix Sums + Hash Map is required here as the window property loses monotonicity).
  • Using it when the order of elements does not matter.

The Problem

The Fundamental Issue

Redundant computation in overlapping sub-ranges. Brute force re-evaluates the entire range for every possible starting index.

What breaks without it

Time Limit Exceeded (TLE) on large inputs (N > 10,000).

Inefficient CPU utilization due to repeated traversals of the same memory blocks.

Why alternatives fail

Brute force is O(N²), which is unacceptable for modern scale.

Sorting breaks the 'contiguous' requirement of the original indices.

Simple recursion without memoization leads to exponential time complexity.

Mental Model

The Intuition

Think of a caterpillar moving across a branch. The head (right pointer) stretches forward to explore new territory, and the tail (left pointer) pulls forward to keep the body length within the constraints of the branch's strength.

Key Mechanics

1

Initialize two pointers: left = 0, right = 0.

2

Expand the 'right' pointer to include elements and update the window state.

3

While the window state violates the constraint, shrink the 'left' pointer and update the state.

4

Capture the result (max/min/count) at each valid step.

Framework

When it's the best choice

  • When the problem involves a 'contiguous' constraint.
  • When the input is a stream and you cannot store all previous elements.
  • When the window property is monotonic (adding an element only increases/decreases the metric).

When to avoid

  • When the data is not linear (e.g., Trees or Graphs, unless it's a specific path).
  • When the window property is non-monotonic (e.g., subarray sum with negative numbers).

Fast Heuristics

If the window size is fixed: Use a single loop with a 'right' pointer and subtract 'right - K'.
If the window size is variable: Use a 'while' loop to shrink the 'left' pointer.
If looking for 'at most K': Solve for 'exactly K' by doing 'f(K) - f(K-1)'.

Tradeoffs

+

Strengths

  • Amortized O(N) time complexity (each element is visited at most twice).
  • Low space overhead, often O(1) if using a fixed-size frequency array.
  • Highly compatible with streaming data.
−

Weaknesses

  • Logic can be tricky to implement without off-by-one errors.
  • Harder to debug than simple nested loops.
  • Requires the problem to have a monotonic property.

Alternatives

Prefix Sums
Alternative

When it wins

When you need to answer multiple range sum queries on a static array.

Key Difference

Prefix Sums take O(N) pre-processing and O(1) per query, whereas Sliding Window is for a single pass search.

Two Pointers
Alternative

When it wins

When the array is sorted and you need to find a pair (e.g., Two Sum II).

Key Difference

Two Pointers usually move from opposite ends toward the center; Sliding Window pointers move in the same direction.

Dynamic Programming
Alternative

When it wins

When the optimal solution for a range depends on non-contiguous subproblems.

Key Difference

DP stores results of all subproblems; Sliding Window only stores the state of the current range.

Execution

Must-hit talking points

  • Mention 'Amortized Analysis' to explain why the nested while-loop is still O(N).
  • Discuss 'Invariants': What must be true about the window at the end of each iteration?
  • Explain the 'Expansion' vs 'Contraction' phases clearly.
  • Identify if the window is 'Fixed' or 'Variable' size immediately.

Anticipate follow-ups

  • Q:How would you handle a data stream where you can't fit the window in memory?
  • Q:Can you optimize the shrinking phase using a Hash Map or a Frequency Array?
  • Q:What if the input array is circular? (Hint: Concatenate the array to itself or use modulo).

Red Flags

Updating the result at the wrong time.

Why it fails: In 'shortest' problems, you update after the while-loop (contraction); in 'longest' problems, you update after the expansion.

Off-by-one errors in window length calculation.

Why it fails: The length of a window from index 'i' to 'j' is '(j - i + 1)', not '(j - i)'.

Forgetting to clear or update the state when the left pointer moves.

Why it fails: The window state becomes desynchronized with the actual elements between the pointers, leading to incorrect results.