Learn › DSA Patterns

Pattern #2 · Arrays & Strings · O(N) Time O(1) Space

Sliding
Window

Turn O(N²) brute force into O(N) by maintaining a running window — add the new element, drop the old one.

🔢 Max sum subarray 🔤 Longest substring 🎯 Minimum window

Scroll to learn

Story Time

The Train Window 🚂🪟

Before writing a single line of code, let's understand the intuition through a story.

🏞️

Sam Counts Sunflowers

Sam is on a train looking at fields passing by. At any moment she can only see 3 consecutive fields through her window. She wants to find the 3-field stretch with the most sunflowers. The fields pass by one at a time: 2, 1, 5, 1, 3, 2.

😩

The Exhausting Way

At first Sam tries the obvious approach: every time the train moves forward one field, she counts all 3 visible fields from scratch. For 6 fields and window size 3, that's 4 windows × 3 counts = 12 operations. For 1,000 fields it becomes nearly 3,000. This is O(N × k) — brute force.

🧙

The Conductor's Trick

The conductor leans over: "Sam, you're doing too much work. When the train moves forward, only one field disappears from the back and one new field appears at the front. Just subtract the old one and add the new one!"

✗ Brute force: re-count all k fields every step → O(N × k)
✓ Sliding window: sum += arr[right] − arr[left−1] → O(N)

📍

Visualising the Window

Array [2, 1, 5, 1, 3, 2] with k = 3. The teal window slides right, updating the sum in O(1) per step:

2 1 5

sum = 8

1 5 1

sum = 7

5 1 3

sum = 9 ← max ✓

1 3 2

sum = 6

🚀

Moral of the story

The window slides one step at a time. Each slide is one addition and one subtraction — no re-scanning. That transforms O(N²) brute force into O(N) sliding window.

Interactive

Window Visualizer

Watch the window slide across [2, 1, 5, 1, 3, 2] with k = 3, finding the max sum.

Initial window [0..2] = [2, 1, 5]. Sum = 2+1+5 = 8. maxSum = 8.

in window max window L left pointer R right pointer

windowSum += arr[right] Expand: add right element

windowSum -= arr[left] Shrink: drop left element

maxSum = Math.max(...) Track best result

Complexity

Three Approaches

Approach	Time	Space	Best for
Nested Loops (Brute)	O(N²)	O(1)	Tiny inputs, clarity
Sliding Window Preferred ✓	O(N)	O(1)–O(k)	Contiguous subarrays
Prefix Sums	O(N)	O(N)	Range-sum queries

Sliding Window needs O(1) extra space for fixed-size windows and O(k) for variable windows (a frequency map of at most k distinct chars).

TypeScript

Implementation

Fixed window → variable window → minimum window.

// Fixed-size Sliding Window — O(N) time, O(1) space
function maxSumSubarray(arr: number[], k: number): number {
  let windowSum = 0;

  // Build the first window of size k
  for (let i = 0; i < k; i++) {
    windowSum += arr[i];
  }
  let maxSum = windowSum;          // first window is the baseline

  // Slide: +new element, −outgoing element  ← the key insight
  for (let i = k; i < arr.length; i++) {
    windowSum += arr[i] - arr[i - k]; // O(1) per slide
    maxSum = Math.max(maxSum, windowSum);
  }

  return maxSum;
}

// [2, 1, 5, 1, 3, 2], k = 3
// Windows: [2+1+5=8] → [1+5+1=7] → [5+1+3=9] ← max → [1+3+2=6]
console.log(maxSumSubarray([2, 1, 5, 1, 3, 2], 3)); // → 9

// Variable Sliding Window — O(N) time, O(min(N,σ)) space
// Longest substring without repeating characters (LeetCode 3)
function lengthOfLongestSubstring(s: string): number {
  const seen = new Map<string, number>(); // char → last seen index
  let maxLen = 0;
  let left   = 0;              // window left pointer

  for (let right = 0; right < s.length; right++) {
    const ch = s[right];

    // Duplicate inside window — shrink left past it
    if (seen.has(ch) && seen.get(ch)! >= left) {
      left = seen.get(ch)! + 1;
    }

    seen.set(ch, right);
    maxLen = Math.max(maxLen, right - left + 1);
  }

  return maxLen;
}

// "abcabcbb" → 3  ("abc")
// "bbbbb"    → 1  ("b")
// "pwwkew"   → 3  ("wke")
console.log(lengthOfLongestSubstring("abcabcbb")); // → 3

// Minimum Window Substring (LC 76) — O(N+M) time, O(σ) space
// Find the smallest window in s that contains every char of t
function minWindow(s: string, t: string): string {
  const need = new Map<string, number>();
  for (const ch of t) need.set(ch, (need.get(ch) ?? 0) + 1);

  let have = 0, required = need.size;
  let left = 0, minLen = Infinity, minStart = 0;
  const win = new Map<string, number>();

  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    win.set(ch, (win.get(ch) ?? 0) + 1);
    if (need.has(ch) && win.get(ch) === need.get(ch)) have++;

    // Shrink from left while all required chars are satisfied
    while (have === required) {
      if (right - left + 1 < minLen) { minLen = right - left + 1; minStart = left; }
      const lch = s[left++];
      win.set(lch, win.get(lch)! - 1);
      if (need.has(lch) && win.get(lch)! < need.get(lch)!) have--;
    }
  }

  return minLen === Infinity ? "" : s.slice(minStart, minStart + minLen);
}

// s = "ADOBECODEBANC", t = "ABC"  →  "BANC"
console.log(minWindow("ADOBECODEBANC", "ABC")); // → "BANC"

Want the full debugging story behind lengthOfLongestSubstring() — six real bugs and how each was found? Read the Longest Substring case study.

Comparison

Nested Loops vs Sliding Window

🔁 Nested Loop Approach O(N²) time

Max sum subarray Re-sum all k elements each step

Longest substring Check every start+end pair

Code simplicity Easy to write

Scalability Fails at N > 10,000

Interviews Acceptable first pass only

🪟 Sliding Window O(N) time

Max sum subarray +new, −old in O(1)

Longest substring Expand right, shrink left

Code simplicity Intuitive once learned

Scalability Handles N = 10,000,000

Interviews Expected optimal solution

Practice

Solve It Yourself

Click any question to see hints and approach.

B Basic

B1 What is the Sliding Window pattern, and what problem does it solve? ⌄

💡 Hint

Think about what makes nested-loop solutions slow for subarray problems. What redundant work do they do?

✅ Answer

The Sliding Window pattern maintains a contiguous window (subarray/substring) that expands or shrinks as it moves through data. It eliminates redundant recomputation: instead of re-processing all k elements each step, it does O(1) work per slide (+new element, −outgoing element). This reduces O(N×k) brute force to O(N).

B2 Given [3, 1, 2, 5, 1, 4], k=3, trace maxSumSubarray step by step. ⌄

💡 Hint

Build the first window [3,1,2]=6, then slide: subtract arr[i−k] and add arr[i] each iteration.

✅ Answer

Init: sum=3+1+2=6, max=6. Step i=3: sum=6−3+5=8, max=8. Step i=4: sum=8−1+1=8, max=8. Step i=5: sum=8−2+4=10, max=10. Answer: 10 (window [5,1,4]).

B3 What is the difference between a fixed-size and a variable-size sliding window? ⌄

💡 Hint

In one, k is given. In the other, you expand until a condition is violated, then shrink.

✅ Answer

Fixed-size window (e.g. max sum of k elements): both pointers advance together — right advances, left = right − k. Variable-size window (e.g. longest substring without repeating chars): right expands greedily; when a constraint is violated, left shrinks until the window is valid again. Variable windows solve problems where the optimal k is unknown.

M Intermediate

M1 LeetCode 643 — Maximum Average Subarray I: given [1,12,-5,-6,50,3], k=4, find max average. ⌄

💡 Hint

Fixed-size window. Build first window sum, then slide. Max average = maxSum / k.

✅ Answer

Window sums: [1+12−5−6=2] → [12−5−6+50=51] → [−5−6+50+3=42]. maxSum=51, average=51/4=12.75. LeetCode expects 12.75.

→ Solve on LeetCode ↗

M2 LeetCode 3 — Longest Substring Without Repeating Characters: find length for "abcabcbb". ⌄

💡 Hint

Variable window. seen map tracks the last index of each char. When right hits a duplicate inside the window, move left to seen[ch]+1.

✅ Answer

right=0:'a'→{a:0},max=1. right=1:'b'→{a:0,b:1},max=2. right=2:'c'→{a:0,b:1,c:2},max=3. right=3:'a'→dup at 0, left=1 → {a:3,b:1,c:2},max=3. right=4:'b'→dup at 1, left=2 → max=3. Answer: 3 ("abc"). This exact problem has a full worked debugging journey (real bugs found and fixed) on the case study page.

→ Read the full case study

M3 LeetCode 209 — Minimum Size Subarray Sum: find shortest subarray with sum ≥ 7 in [2,3,1,2,4,3]. ⌄

💡 Hint

Variable window. Expand right greedily; once sum ≥ target, record length and shrink from left while still valid.

✅ Answer

Expand until sum≥7: [2,3,1,2] sum=8≥7, len=4. Shrink: drop 2 → [3,1,2] sum=6<7. Expand: [3,1,2,4] sum=10≥7, len=4. Shrink: drop 3→[1,2,4] sum=7≥7 len=3. Drop 1→[2,4] sum=6<7. Expand: [2,4,3] sum=9≥7 len=3. Drop 2→[4,3] sum=7≥7 len=2 ← min. Answer: 2.

→ Solve on LeetCode ↗

H Advanced

H1 LeetCode 76 — Minimum Window Substring: find smallest window in "ADOBECODEBANC" containing "ABC". ⌄

💡 Hint

Use a need map for t and a window map. Expand right; when have===required, record size and shrink left. The inner while loop is amortized O(1) per char.

✅ Answer

"BANC" (length 4). The two-pointer expand/contract approach: right expands until all of {A,B,C} are in the window, then left contracts to minimize. Each char is visited at most twice (once by right, once by left), giving O(N+M) total.

→ Solve on LeetCode ↗

H2 LeetCode 567 — Permutation in String: does "ab" have a permutation inside "eidbaooo"? ⌄

💡 Hint

Fixed-size window of size s1.length. Compare char frequency maps. Use a count of 'matched' char frequencies to avoid O(26) map comparison each step.

✅ Answer

Yes — 'ba' at index 3. Use a fixed window of size 2 over s2. Maintain freq map of s1 and a window map. Track how many of the 26 chars have equal frequencies. When matches===26, a permutation exists. Slide window: update both maps and recompute matches in O(1).

→ Solve on LeetCode ↗

H3 LeetCode 239 — Sliding Window Maximum: find max in each window of size k for [1,3,-1,-3,5,3,6,7], k=3. ⌄

💡 Hint

A plain max-tracking approach is O(N²). Use a monotonic deque: maintain indices in decreasing value order. The front is always the max. Remove indices outside the window from the front; remove smaller elements from the back.

✅ Answer

Output: [3,3,5,5,6,7]. Deque stores indices in decreasing order of values. For each right: pop back while nums[back]≤nums[right]. Pop front if index ≤ right−k. The front index gives the max for each window. Each element is pushed and popped at most once: O(N).

→ Solve on LeetCode ↗

H4 LeetCode 438 — Find All Anagrams in a String: find all start indices of p's anagrams in s="cbaebabacd", p="abc". ⌄

💡 Hint

Same as LC 567 but collect all valid window positions. Fixed window of size p.length, slide through s.

✅ Answer

[0, 6]. Window size 3: 'cba'→freq matches 'abc' ✓ → index 0. 'bae'→no. 'aeb'→no. 'eba'→no. 'bab'→no. 'aba'→no. 'bac'→freq matches 'abc' ✓ → index 6. 'acd'→no. All anagram starts: [0, 6].

→ Solve on LeetCode ↗

In the Wild

Real-World Applications

📊

Analytics Dashboards

Rolling Averages

Monitoring dashboards display 7-day or 30-day moving averages of metrics like DAU, revenue, and error rates. Recomputing from scratch each second would be O(N × window) — sliding window keeps it O(N).

🪟 How it fits: Maintain a running sum. Each new data point: sum += newValue − expiredValue. Average = sum / windowSize.

🔒

API Gateways

Rate Limiting

Services like Stripe and Cloudflare limit requests to N per second/minute. Counting all timestamps in the last T seconds for every request is slow — a sliding window over a sorted timestamp queue solves it in O(1).

🪟 How it fits: Window = the last T seconds. On each request: pop timestamps older than (now − T) from the front, push current timestamp, check if count ≤ limit.

🌐

Network Monitoring

Anomaly Detection

Network intrusion detection systems (IDS) flag bursts: more than X packets in the last Y milliseconds from the same source. Scanning all packets on every event is impractical at line rate.

🪟 How it fits: A sliding timestamp window per source IP tracks burst counts in O(1) amortized. Packets outside the window are dropped from the front as time advances.

🧬

Bioinformatics

DNA Sequence Search

Finding all occurrences of a short gene pattern in a genome with 3 billion base pairs. Comparing the full pattern character-by-character at each position is O(N × M) — Rabin-Karp uses a sliding hash window.

🪟 How it fits: Hash the pattern and the first window, then roll the hash forward: remove leftmost char, add rightmost. O(1) per position. Total: O(N+M).

Quick Reference

Cheat Sheet

The Patterns

Fixed window

right = left + k − 1

Expand right

sum += arr[right]

Shrink left

sum -= arr[left++]

Window size

right − left + 1

When to Use

✓ Max/min sum of subarray of size k
✓ Longest substring with constraint
✓ Smallest subarray with sum ≥ target
✓ Count subarrays meeting criteria
✓ Permutation / anagram in string
✓ Minimum window containing all chars
✓ Average of all k-length subarrays
✓ Distinct chars in every window

Window Types

Fixed Size

k given. Slide both pointers together. O(1) space.

Variable (expand/shrink)

right expands; left shrinks on violation. O(σ) space.

Complexity

Time: O(N) — each element enters and leaves once

Space: O(1) fixed / O(k) variable

Keep Learning

You've mastered Sliding Window 🎉

This pattern powers rate limiting, rolling analytics, and substring search — all in O(N) time with a clean two-pointer loop.

← Back to Learn LeetCode Sliding Window Problems ↗