Pattern #3 — Sliding Window 🪟

Pattern #3 — Sliding Window 🪟

If I had to pick the single most useful pattern for interviews, it might be this one. It turns slow, nested-loop solutions over subarrays and substrings into fast, single-pass ones.

1. The Idea (in one line)

Keep a "window" (a range) over the array, and slide it along instead of recomputing from scratch.

   Real-life analogy 🚌
   ────────────────────
   Imagine looking out a moving bus window. As the bus moves,
   ONE new thing enters your view on the right, and ONE thing
   leaves on the left. You don't re-look at the whole street —
   you just adjust for what entered and what left.

   → That's the window sliding. Add the new, remove the old.

2. The Picture

   Array: [ 2  1  5  1  3  2 ],  window size k = 3

   window [2  1  5] 1  3  2      sum = 8
           ─────────
            2 [1  5  1] 3  2      slide right:
              ─────────           remove 2 (left), add 1 (right)
                                  new sum = 8 - 2 + 1 = 7

              2  1 [5  1  3] 2    remove 1, add 3 → 7 - 1 + 3 = 9
                   ─────────

   👉 We NEVER re-add the whole window. Just +new -old. O(n)!

3. Two Types of Window

   A) FIXED window  → size is given ("window of size k")
      Both edges move together, one step at a time.

   B) DYNAMIC window → size grows and shrinks based on a rule
      ("longest substring with no repeats", "smallest subarray
       with sum ≥ target")
      Right edge EXPANDS to include more,
      Left edge SHRINKS when a rule is broken.

4. 🔍 How to SPOT This Pattern

   Use Sliding Window when you see:
   ✅ "subarray" or "substring"  (must be CONTIGUOUS!)
   ✅ "longest / shortest / maximum / minimum ... that satisfies X"
   ✅ "window of size k"
   ✅ "at most K distinct", "no repeating characters"
   ✅ You're about to write nested loops over every subarray → stop!

5. Worked Example — Longest Substring Without Repeating Characters

   s = "abcabcbb"

   We grow the window to the right, and if we hit a repeat,
   we shrink from the left until the repeat is gone.

   [a]bcabcbb          window "a"      len 1
   [ab]cabcbb          window "ab"     len 2
   [abc]abcbb          window "abc"    len 3 ← best so far
   [abca]bcbb          'a' repeats! shrink left →
    [bca]bcbb          window "bca"    len 3
     ... keeps going, best stays 3

   Answer: 3  ("abc")

6. The Code Templates 📝

   // A) FIXED window — max sum of any k elements
   function maxSum(nums, k) {
     let sum = 0, best = 0;
     for (let i = 0; i < k; i++) sum += nums[i];   // first window
     best = sum;
     for (let i = k; i < nums.length; i++) {
       sum += nums[i] - nums[i - k];   // add new, remove old
       best = Math.max(best, sum);
     }
     return best;
   }

   // B) DYNAMIC window — longest substring, no repeats
   function longestUnique(s) {
     const seen = new Set();
     let left = 0, best = 0;
     for (let right = 0; right < s.length; right++) {
       while (seen.has(s[right])) {   // rule broken → shrink
         seen.delete(s[left]);
         left++;
       }
       seen.add(s[right]);            // grow
       best = Math.max(best, right - left + 1);
     }
     return best;
   }

7. Practice Problems

   ⭐ Easy / Warm-up
   • Maximum Sum Subarray of Size K
   • Average of Subarrays of Size K

   ⭐⭐ Medium
   • Longest Substring Without Repeating Characters
   • Longest Substring with At Most K Distinct Characters
   • Minimum Size Subarray Sum (≥ target)
   • Permutation in String / Find All Anagrams

8. ⚠️ Common Mistake

   ❌ Using sliding window on a NON-contiguous problem.
      Sliding window only works when the answer must be a
      CONTIGUOUS block. "Pick any k elements" (not contiguous)
      is NOT a sliding-window problem.

Key Takeaway

   Sliding Window = a moving range. Add what enters, remove what
   leaves — never recompute the whole thing. The #1 tool for
   contiguous subarray/substring problems. O(n) instead of O(n²).

Next: Pattern #4 — Merge Intervals, for anything about overlapping time ranges. ⏱️