Sliding Window Pattern

0/14 in this phase0/57 across the roadmap

📖 Concept

The sliding window pattern maintains a "window" (subarray/substring) that expands and contracts as you iterate. It's one of the most powerful patterns for substring and subarray problems.

Two types:

1. Fixed-size window:

Window size is given (e.g., "maximum sum of subarray of size k")
Slide the window by adding the right element and removing the left element
O(n) — each element enters and leaves the window once

2. Variable-size window:

Expand right to include more elements
Shrink left when a condition is violated
Track the optimal window (min length, max length, etc.)
O(n) — right pointer moves n times, left pointer moves at most n times total

Variable window template:

let left = 0;
for (let right = 0; right < n; right++) {
  // Add arr[right] to window
  while (window violates condition) {
    // Remove arr[left] from window
    left++;
  }
  // Update answer with current valid window
}

When to use sliding window:

"Find longest/shortest subarray/substring with property X"
"Maximum/minimum sum of subarray of size K"
"Contains all characters of target string"
Contiguous sequence problems

🏠 Real-world analogy: Sliding window is like reading with a magnifying glass that you slide across text. You control the size of the lens — zoom in (shrink) or zoom out (expand) — to find the section you're looking for.

💻 Code Example

codeTap to expand ⛶

1// FIXED WINDOW — Max sum subarray of size k
2function maxSumSubarray(arr: number[], k: number): number {
3  let windowSum = 0, maxSum = -Infinity;
4  for (let i = 0; i < arr.length; i++) {
5    windowSum += arr[i];           // Add right element
6    if (i >= k) windowSum -= arr[i - k]; // Remove left element
7    if (i >= k - 1) maxSum = Math.max(maxSum, windowSum);
8  }
9  return maxSum;
10}
11
12// VARIABLE WINDOW — Longest substring without repeating chars
13function longestUnique(s: string): number {
14  const seen = new Set<string>();
15  let left = 0, maxLen = 0;
16  for (let right = 0; right < s.length; right++) {
17    while (seen.has(s[right])) {
18      seen.delete(s[left]);
19      left++;
20    }
21    seen.add(s[right]);
22    maxLen = Math.max(maxLen, right - left + 1);
23  }
24  return maxLen;
25}
26
27// VARIABLE WINDOW — Minimum window substring
28function minWindow(s: string, t: string): string {
29  const need = new Map<string, number>();
30  for (const c of t) need.set(c, (need.get(c) || 0) + 1);
31
32  let have = 0, required = need.size;
33  let left = 0, minLen = Infinity, minStart = 0;
34  const window = new Map<string, number>();
35
36  for (let right = 0; right < s.length; right++) {
37    const c = s[right];
38    window.set(c, (window.get(c) || 0) + 1);
39    if (need.has(c) && window.get(c) === need.get(c)) have++;
40
41    while (have === required) {
42      if (right - left + 1 < minLen) {
43        minLen = right - left + 1;
44        minStart = left;
45      }
46      const lc = s[left];
47      window.set(lc, window.get(lc)! - 1);
48      if (need.has(lc) && window.get(lc)! < need.get(lc)!) have--;
49      left++;
50    }
51  }
52  return minLen === Infinity ? "" : s.substring(minStart, minStart + minLen);
53}
54
55// FIXED WINDOW — Find all anagrams of pattern in string
56function findAnagrams(s: string, p: string): number[] {
57  const result: number[] = [];
58  const need = new Array(26).fill(0);
59  const have = new Array(26).fill(0);
60  const a = 'a'.charCodeAt(0);
61
62  for (const c of p) need[c.charCodeAt(0) - a]++;
63
64  for (let i = 0; i < s.length; i++) {
65    have[s.charCodeAt(i) - a]++;
66    if (i >= p.length) have[s.charCodeAt(i - p.length) - a]--;
67    if (have.toString() === need.toString()) result.push(i - p.length + 1);
68  }
69  return result;
70}

🏋️ Practice Exercise

Practice Problems (Easy → Hard):

Maximum sum subarray of size k (fixed window)
Longest substring without repeating characters
Find all anagrams of a pattern in a string
Longest substring with at most k distinct characters
Minimum size subarray with sum ≥ target
Maximum number of vowels in a substring of size k
Longest repeating character replacement (with at most k changes)
Minimum window substring (contains all chars of target)
Sliding window maximum (use deque for O(n))
Subarrays with k different integers

⚠️ Common Mistakes

Not recognizing when sliding window applies — look for 'contiguous subarray/substring' keywords
Forgetting to shrink the window — the left pointer must move to maintain the window condition
Using O(n) comparison in the loop (e.g., comparing full hash maps) — use counters instead for O(1)
Confusing fixed and variable window — fixed: always size k, variable: shrink/expand to optimize
Not updating the answer at the right time — update AFTER ensures condition, not before

💼 Interview Questions

🎤 Mock Interview

Practice a live interview for Sliding Window Pattern

Was this topic helpful?

← PreviousTwo Pointers Pattern Next →Prefix Sum & Range Queries