Coding

Sliding window

Expand/contract a window to maintain a constraint.

Coding pattern

Overview

Sliding window solves 'best contiguous sub-range' questions by growing a window until a constraint breaks, then shrinking from the left to restore it. It converts recomputing every substring into an amortized single pass.

How it works

Coding pattern

ClientEdgeServiceData

Step by step, with examples

1
Sequence
- A contiguous sub-range problem over array/string.
2
Grow right
- Extend the window until the constraint breaks.
3
Move left
- Contract from the left to restore validity.
4
Best window
- Record the max/min length or sum seen.
- Example: Longest substring, k distinct

When to reach for it

Longest/shortest substring
Subarray with a condition
Fixed-size windows

Example problem

Longest substring without repeating characters.

Approach

Grow the right edge
When a dup appears, shrink from the left
Track the max window

Solution

function lengthOfLongest(s) {
  const seen = new Set();
  let left = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    while (seen.has(s[right])) seen.delete(s[left++]);
    seen.add(s[right]);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

Complexity

Time O(n), Space O(min(n, charset)).

Common pitfalls

Not shrinking enough
Resetting state incorrectly

Where this content comes from

For full transparency, this content is curated and verified from these sources:

Curated company-tagged problem banksRecurring interview pattern librariesOppZen-authored drills & solutions