Chapter 07 — Sliding Window

Chapter 07 — Sliding Window

Hey everyone! Welcome back to Namaste DSA!

Whenever you see "subarray" or "substring" with words like longest, shortest, maximum, or of size k — your brain should shout Sliding Window! Instead of recomputing each window from scratch (slow), you slide a window across the data and reuse the previous work.

What we will cover:

• The sliding window idea
• Fixed-size window (max sum of k elements)
• Variable-size window (longest substring without repeats)
• Expand & shrink mechanics
• Window vs two pointers
• Interview Questions

---

1. The Sliding Window Idea

┌─────────────────────────────────────────────────────────────┐
│   NAIVE: recompute every window → O(n·k) or O(n²)          │
│   SLIDE: add the new element, remove the old one → O(n)     │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│   [ 2  1  5  1  3  2 ]   window size k = 3                  │
│    └──────┘                sum = 8                          │
│       └──────┘             slide: -2 +1 → reuse!            │
│          └──────┘                                           │
│                                                             │
│   Don't re-add everything — just adjust the edges.          │
└─────────────────────────────────────────────────────────────┘

---

2. Fixed-Size Window — Max Sum of k Elements

function maxSumK(arr, k) {
    let windowSum = 0;
    // build the first window
    for (let i = 0; i < k; i++) windowSum += arr[i];

    let best = windowSum;
    // slide: add right edge, remove left edge
    for (let i = k; i < arr.length; i++) {
        windowSum += arr[i] - arr[i - k];
        best = Math.max(best, windowSum);
    }
    return best;
}

HAND TRACE: maxSumK([2, 1, 5, 1, 3, 2], 3)

  first window [2,1,5] → sum = 8, best = 8
  i=3: +arr[3](1) -arr[0](2) → 8+1-2 = 7   best=8
  i=4: +arr[4](3) -arr[1](1) → 7+3-1 = 9   best=9   ← [5,1,3]
  i=5: +arr[5](2) -arr[2](5) → 9+2-5 = 6   best=9
  answer = 9 ✔   (in O(n), not O(n·k))

---

3. Variable-Size Window — Longest Substring Without Repeating Characters

Here the window grows and shrinks. Expand the right edge; if a duplicate appears, shrink from the left until the window is valid again.

function longestUnique(s) {
    const seen = new Set();
    let left = 0, best = 0;
    for (let right = 0; right < s.length; right++) {
        // shrink until s[right] is no longer a duplicate
        while (seen.has(s[right])) {
            seen.delete(s[left]);
            left++;
        }
        seen.add(s[right]);
        best = Math.max(best, right - left + 1);
    }
    return best;
}

HAND TRACE: longestUnique("abcabcbb")

  r=0 'a' → win "a"    best=1
  r=1 'b' → win "ab"   best=2
  r=2 'c' → win "abc"  best=3
  r=3 'a' → dup! shrink: drop 'a'(left=1) → win "bca" best=3
  r=4 'b' → dup! shrink: drop 'b'(left=2) → win "cab" best=3
  ... best stays 3
  answer = 3  ("abc") ✔

---

4. The Expand & Shrink Template

┌─────────────────────────────────────────────────────────────┐
│            VARIABLE WINDOW TEMPLATE                          │
├─────────────────────────────────────────────────────────────┤
│  left = 0                                                    │
│  for right in 0..n-1:                                        │
│      add arr[right] to the window                            │
│      while (window is INVALID):                              │
│          remove arr[left]; left++                            │
│      update answer with current window                       │
└─────────────────────────────────────────────────────────────┘

The "is invalid?" condition changes per problem (too many distinct chars, sum too big, etc.), but the skeleton is always this.

---

5. Sliding Window vs Two Pointers

	Two Pointers	Sliding Window
Pointers move	Often toward each other	Both forward; gap = the window
Best for	Pairs in sorted data	Contiguous subarray/substring
Tracks	Two positions	A range + running state (sum/set)

Sliding window is really a special two-pointer pattern where both pointers move the same direction and you care about the contiguous range between them.

---

Interview Questions — Quick Fire!

Q: When should you use a sliding window?

"For problems about contiguous subarrays or substrings — finding the longest, shortest, or best window meeting some condition, or any fixed-size-k window question. It avoids recomputing each window by reusing the previous one, turning O(n·k) or O(n²) into O(n)."

Q: What's the difference between a fixed and variable sliding window?

"A fixed window has a constant size k — you slide it one step at a time, adding the new element and removing the oldest. A variable window grows by expanding the right edge and shrinks by moving the left edge whenever the window becomes invalid, like when a duplicate appears."

Q: Why is longest-substring-without-repeats O(n) and not O(n²)?

"Because each character is added to the window once and removed at most once. The left and right pointers only move forward, so total pointer movement is at most 2n — that's O(n), even though there's a nested while loop."

Q: How does the window stay valid?

"After expanding the right edge, you run a while loop that shrinks from the left until the window satisfies the constraint again. The exact constraint depends on the problem — no duplicates, sum below a limit, at most k distinct characters, and so on."

---

Quick Recap

Concept	Key Takeaway
Idea	Reuse work — slide, don't recompute.
Fixed window	Add right edge, remove left edge.
Variable window	Expand right, shrink left while invalid.
Complexity	O(n) — each element enters/leaves once.
Trigger words	"subarray/substring", "longest", "size k".

What's Next?

Chapter 08: Linked Lists — our first pointer-based data structure. We'll reverse one (the #1 interview question), find its middle, and detect cycles with the fast/slow pointers you just met.

Keep coding, keep grinding! See you in the next one!