🪟 Sliding Window Patterns: The Magic Window That Glides!

🎬 Once Upon a Time in Array Land…

Imagine you’re looking through a window on a train. As the train moves, you see different parts of the beautiful landscape. You don’t jump off the train to see each tree one by one—that would be exhausting! Instead, your window slides smoothly along, showing you new scenery while the old scenery disappears behind you.

That’s exactly what a Sliding Window does with arrays!

Instead of checking every possible group of elements (super slow!), we slide a “window” across the array. As we move forward, we add one new element and remove one old element. Simple, fast, and magical! ✨

🎯 Why Sliding Window is Your New Best Friend

📦 Pattern 1: Fixed Size Window

The Story

Imagine you have a row of 10 cookies with different yummy ratings. You can only eat 3 cookies at a time (that’s your window size). You want to find which group of 3 cookies gives you the maximum yumminess!

How It Works

// Array of yummy ratings
let cookies = [2, 1, 5, 1, 3, 2];
// Window size = 3

// Step 1: Sum first window
// [2, 1, 5] = 8

// Step 2: Slide! Remove 2, Add 1
// [1, 5, 1] = 8 - 2 + 1 = 7

// Step 3: Slide! Remove 1, Add 3
// [5, 1, 3] = 7 - 1 + 3 = 9 ✨ MAX!

// Step 4: Slide! Remove 5, Add 2
// [1, 3, 2] = 9 - 5 + 2 = 6

The Code

function maxSumFixed(arr, k) {
  // k = fixed window size
  let maxSum = 0;
  let windowSum = 0;

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

  // Slide the window
  for (let i = k; i < arr.length; i++) {
    // Add new element, remove old
    windowSum += arr[i] - arr[i - k];
    maxSum = Math.max(maxSum, windowSum);
  }

  return maxSum;
}

// Example
maxSumFixed([2, 1, 5, 1, 3, 2], 3);
// Returns: 9

The Magic Formula

New Window Sum = Old Sum + New Element - Old Element

It’s like trading one cookie for another! 🍪↔️🍪

🔄 Pattern 2: Variable Size Window

The Story

Now imagine you’re collecting stars ⭐ in a game. You need to collect stars until you have at least 7 stars, but you want to use the smallest basket possible (fewest moves).

Your window grows when you need more stars, and shrinks when you have enough!

How It Works

graph TD
    A["Start: Empty Window"] --> B["Expand → Add elements"]
    B --> C{"Condition met?"}
    C -->|No| B
    C -->|Yes| D["Record answer"]
    D --> E["Shrink → Remove from left"]
    E --> C

The Code Pattern

function variableWindow(arr, target) {
  let left = 0;
  let right = 0;
  let windowSum = 0;
  let minLength = Infinity;

  while (right < arr.length) {
    // EXPAND: Add element at right
    windowSum += arr[right];

    // SHRINK: While condition is met
    while (windowSum >= target) {
      // Record answer
      minLength = Math.min(
        minLength,
        right - left + 1
      );
      // Remove from left
      windowSum -= arr[left];
      left++;
    }

    right++;
  }

  return minLength === Infinity
    ? 0
    : minLength;
}

Two Pointers Dance 💃🕺

[2, 3, 1, 2, 4, 3]  Target: 7

left↓
[2, 3, 1, 2, 4, 3]  Sum: 2
     right↑

    left↓
[2, 3, 1, 2, 4, 3]  Sum: 5
        right↑

       left↓
[2, 3, 1, 2, 4, 3]  Sum: 8 ≥ 7!
           right↑
           Length = 4, shrink!

         left↓
[2, 3, 1, 2, 4, 3]  Sum: 6, expand...
           right↑

🎯 Pattern 3: Minimum Size Subarray Sum

The Problem

Given an array of positive numbers and a target sum, find the smallest subarray whose sum is ≥ target.

Real-Life Example

You’re downloading files. Each file takes different seconds:

Files: [2, 3, 1, 2, 4, 3] seconds
Target: Download at least 7 seconds worth
Question: What's the minimum number of files?

The Solution

function minSubArrayLen(target, nums) {
  let left = 0;
  let sum = 0;
  let minLen = Infinity;

  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];  // Expand

    while (sum >= target) {
      // Found valid window!
      minLen = Math.min(minLen, right - left + 1);
      sum -= nums[left]; // Shrink
      left++;
    }
  }

  return minLen === Infinity ? 0 : minLen;
}

// Example
minSubArrayLen(7, [2, 3, 1, 2, 4, 3]);
// Answer: 2 (because [4, 3] = 7)

Step-by-Step Walkthrough

Answer: 2 (The subarray [4, 3] sums to 7!)

🏔️ Pattern 4: Sliding Window Maximum

The Problem

Given an array and window size k, find the maximum element in each window as it slides.

The Story

Imagine you’re a lifeguard watching k swimmers at a time. As new swimmers enter your zone and old ones leave, you need to know: Who’s the tallest swimmer right now?

Simple Approach (Works but Slow)

function maxSlidingWindowSimple(nums, k) {
  let result = [];

  for (let i = 0; i <= nums.length - k; i++) {
    let window = nums.slice(i, i + k);
    result.push(Math.max(...window));
  }

  return result;
}

Problem: This is O(n × k) — too slow for big arrays!

Smart Approach: Monotonic Deque 🎢

A deque (double-ended queue) is like a line where people can join or leave from both ends.

We keep our deque monotonic decreasing — the biggest person is always at the front!

function maxSlidingWindow(nums, k) {
  let result = [];
  let deque = []; // Stores indices

  for (let i = 0; i < nums.length; i++) {
    // Remove indices outside window
    if (deque.length && deque[0] < i - k + 1) {
      deque.shift();
    }

    // Remove smaller elements
    // (they'll never be maximum)
    while (
      deque.length &&
      nums[deque[deque.length - 1]] < nums[i]
    ) {
      deque.pop();
    }

    // Add current index
    deque.push(i);

    // Record maximum (front of deque)
    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }

  return result;
}

Visual Example

Array: [1, 3, -1, -3, 5, 3, 6, 7]
Window size k = 3

Window [1, 3, -1]  → Max = 3
       [3, -1, -3] → Max = 3
       [-1, -3, 5] → Max = 5
       [-3, 5, 3]  → Max = 5
       [5, 3, 6]   → Max = 6
       [3, 6, 7]   → Max = 7

Result: [3, 3, 5, 5, 6, 7]

Why Deque Works

graph TD
    A["New element arrives"] --> B{"Is it bigger than<br>back of deque?"}
    B -->|Yes| C["Pop from back"]
    C --> B
    B -->|No| D["Push to back"]
    D --> E{"Is front outside<br>window?"}
    E -->|Yes| F["Remove from front"]
    E -->|No| G["Front = Maximum!"]
    F --> G

🎨 The Pattern Recognition Chart

🧠 Key Takeaways

1. Fixed Window: Size stays the same, just slide and update
2. Variable Window: Two pointers — expand right, shrink left
3. Min Size Subarray: Find smallest window meeting condition
4. Sliding Maximum: Use a deque to track potential maximums

🌟 The Golden Rule

“Never recalculate what you can just update!”

Every time you slide:

• Add the new element entering the window
• Remove the old element leaving the window
• Update your answer

That’s the magic of Sliding Window! 🪟✨