/Projects
Coding patterns · 02 of 15

Sliding window

Grow the right edge, shrink the left edge while invalid.

PracticeCoding patternTier 2 · MechanismsApply15 minCore engineering

You will be able to: spot sliding window from a problem statement, and code it from memory.

Interview prepCoding patterns

Study with AI

O(n) time, O(k) space for the window state Watch as reels
Part 1 of 5

Basics

The idea behind the pattern, why it is correct, and the clues in a question that point to it.

1.1Core idea

What the pattern does, in plain words.

Keep a window [left, right]. Extend right one step at a time and update counts. While the window breaks the rule, move left forward. Every index enters and leaves once.

Why it works

A window from left to right holds the current candidate. Moving right adds one element and moving left removes one, so counts are updated in O(1) instead of recomputing every subarray. Each index enters and leaves the window at most once, which gives O(n).

Typical cost: O(n) time, O(k) space for the window state

1.2Recognition signals

If a question has one of these clues, try this pattern first.

Contiguous subarray or substringLongest or shortest window with a propertyAt most K distinct, no repeats, sum at least S
Part 2 of 5

Question

A classic interview problem from this family. Read it carefully and plan the approach before writing any code.

2.1Minimum Window Substring

The problem statement, then the plan you would say out loud.

Problem

Find the smallest substring of s that contains every character of t (with multiplicity).

Plan before you code

  1. Count what t needs.
  2. Expand right; when a need is met, decrement 'missing'.
  3. While nothing is missing, record the window and shrink from the left.
Part 3 of 5

Detailed answer

First the reusable template, then the worked solution built from it and a walk through it one step at a time.

3.1Template

Memorise this shape. Most problems in this family are this code plus one twist.

Longest window that satisfies a rule

longest-window-that.tsTypeScript
1function longestWindow(s: string): number {2  const count = new Map<string, number>();3  let left = 0, best = 0;4  for (let right = 0; right < s.length; right++) {5    const ch = s[right];6    count.set(ch, (count.get(ch) ?? 0) + 1);7    while (count.get(ch)! > 1) {   // window invalid8      count.set(s[left], count.get(s[left])! - 1);9      left++;10    }11    best = Math.max(best, right - left + 1);12  }13  return best;14}
14 linesUTF-8TypeScript
  1. Extend the right edge and record the new character.
  2. Shrink from the left until the window is valid again.
  3. Every valid window is a candidate answer.

3.2Solution

Strict TypeScript, type-checked and tested.

Minimum Window Substring

minimum-window-substring.tsTypeScript
1function minWindow(s: string, t: string): string {2  const need = new Map<string, number>();3  for (const ch of t) need.set(ch, (need.get(ch) ?? 0) + 1);4  let missing = t.length;5  let left = 0, bestLo = 0, bestLen = Infinity;6  for (let right = 0; right < s.length; right++) {7    const ch = s[right];8    if ((need.get(ch) ?? 0) > 0) missing--;9    need.set(ch, (need.get(ch) ?? 0) - 1);10    while (missing === 0) {11      if (right - left + 1 < bestLen) {12        bestLo = left;13        bestLen = right - left + 1;14      }15      const out = s[left++];16      need.set(out, need.get(out)! + 1);17      if (need.get(out)! > 0) missing++;18    }19  }20  return bestLen === Infinity ? "" : s.slice(bestLo, bestLo + bestLen);21}
21 linesUTF-8TypeScript

Step by step

  1. need counts what t requires; missing is how many are still owed.
  2. Grow right and pay off a need when you can.
  3. Window covers t: keep it if it is the smallest so far.
  4. Shrink left; giving back a needed character breaks the window.

Complexity: O(|s| + |t|) time, O(alphabet) space

Part 4 of 5

Q&A

What interviewers ask once your code works, and problems to try on your own.

4.1Interview questions

Answer out loud, then open.

When does a sliding window fail?
When shrinking the window does not reliably move it towards valid, for example sums with negative numbers. Use prefix sums with a hash map there.
Fixed or variable window?
Fixed size k: move both ends together. Variable: grow right, and shrink left while the window breaks the rule (for the longest) or while it still satisfies it (for the shortest).
How do you know every required character is covered in O(1)?
Keep a count of how many required characters are still missing, and update it only when a character's count crosses zero.

4.2Solo practice

Try these without looking; open the hint only when stuck.

EasyMaximum Sum Subarray of Size K
Hint

Fixed-size window: add right, subtract the element leaving.

Part 5 of 5

Extra depth

More fully worked problems in the same family, and the mistakes that cost offers.

5.12 more worked problems

Each one: the problem, the plan, the code and its cost.

Show detailsHide details
Medium

Longest Repeating Character Replacement

Replace at most k characters to get the longest run of one letter.

  1. A window is valid if length − (count of its most common letter) ≤ k.
  2. Grow right; shrink left while invalid.
  3. The max count never needs to decrease for the answer to stay correct.
longest-repeating-character.tsTypeScript
1function characterReplacement(s: string, k: number): number {2  const count = new Map<string, number>();3  let left = 0, top = 0, best = 0;4  for (let right = 0; right < s.length; right++) {5    const c = (count.get(s[right]) ?? 0) + 1;6    count.set(s[right], c);7    top = Math.max(top, c);8    while (right - left + 1 - top > k) {9      count.set(s[left], count.get(s[left])! - 1);10      left++;11    }12    best = Math.max(best, right - left + 1);13  }14  return best;15}
15 linesUTF-8TypeScript

Complexity: O(n) time, O(1) space (26 letters)

Hard

Sliding Window Maximum

Return the maximum of every window of size k.

  1. Keep a deque of indices whose values are decreasing.
  2. A new value evicts smaller ones: they can never be a maximum again.
  3. The front is the maximum; drop it when it leaves the window.
sliding-window-maximum.tsTypeScript
1function maxSlidingWindow(nums: number[], k: number): number[] {2  const dq: number[] = [];   // indices; values decrease from head to back3  let head = 0;4  const out: number[] = [];5  for (let i = 0; i < nums.length; i++) {6    while (dq.length > head && nums[dq[dq.length - 1]] <= nums[i]) dq.pop();7    dq.push(i);8    if (dq[head] <= i - k) head++;9    if (i >= k - 1) out.push(nums[dq[head]]);10  }11  return out;12}
12 linesUTF-8TypeScript

Complexity: O(n) time, O(k) space

5.2Traps

Bugs and misreadings that come up again and again with this pattern.

Show detailsHide details
  • Using a window on non-contiguous problems
  • Shrinking with if instead of while
  • Off-by-one in window length (right - left + 1)
AI Engineer · Sliding window