🪟 Sliding Window Patterns: The Magic Window Technique

🎭 The Story of the Curious Window

Imagine you’re looking through a small window on a moving train. You can only see a little bit of the world at a time. As the train moves, your view shifts—old scenery slides out, new scenery slides in.

This is exactly how the Sliding Window technique works in programming!

Instead of looking at an entire array again and again (slow!), we look through a “window” and slide it along—keeping what we need, dropping what we don’t.

🧩 Why Sliding Window?

❌ Brute Force: Check EVERY possible subarray
   → Slow like reading the whole book for each question

✅ Sliding Window: Slide and adjust smartly
   → Fast like moving your bookmark as you read

📐 Pattern 1: Fixed Size Sliding Window

The Idea

Your window has a fixed size (like a photo frame). You slide it across the array one step at a time.

Real Life Example

You have a row of 10 ice cream shops. You want to find the 3 consecutive shops that sell the most ice cream together.

How It Works

graph TD
    A["Array: [2,1,5,1,3,2]"] --> B["Window size = 3"]
    B --> C["Window 1: [2,1,5] = 8"]
    C --> D["Window 2: [1,5,1] = 7"]
    D --> E["Window 3: [5,1,3] = 9 ✓"]
    E --> F["Window 4: [1,3,2] = 6"]
    F --> G["Max Sum = 9"]

Java Code

int maxSum(int[] arr, int k) {
    int n = arr.length;
    if (n < k) return -1;

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

    int maxSum = windowSum;

    // Slide: add new, remove old
    for (int i = k; i < n; i++) {
        windowSum += arr[i];      // add new
        windowSum -= arr[i - k];  // remove old
        maxSum = Math.max(maxSum, windowSum);
    }

    return maxSum;
}

Key Insight

Add one at the front, remove one from the back. Like a caterpillar moving forward!

📏 Pattern 2: Variable Size Sliding Window

The Idea

Now your window can stretch and shrink like a rubber band! You expand it to grab more, shrink it when you’ve grabbed too much.

Real Life Example

Find the shortest line of people at a store whose combined money is at least $100.

How It Works

graph TD
    A["Goal: Find smallest window ≥ target"]
    A --> B["Expand window #40;add right#41;"]
    B --> C{Sum ≥ target?}
    C -->|No| B
    C -->|Yes| D["Shrink window #40;remove left#41;"]
    D --> E["Record size if smaller"]
    E --> C

The Two-Pointer Dance

LEFT pointer → shrinks the window
RIGHT pointer → expands the window

They never cross. They dance together!

🎯 Pattern 3: Minimum Size Subarray Sum

The Problem

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

Example

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

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

Visual Walkthrough

[2, 3, 1, 2, 4, 3]  target=7
 ↑
 L,R  sum=2 (too small, expand)

[2, 3, 1, 2, 4, 3]
 ↑  ↑
 L  R  sum=5 (too small, expand)

[2, 3, 1, 2, 4, 3]
 ↑     ↑
 L     R  sum=6 (too small, expand)

[2, 3, 1, 2, 4, 3]
 ↑        ↑
 L        R  sum=8 ≥7 ✓ (size=4, shrink!)

[2, 3, 1, 2, 4, 3]
    ↑     ↑
    L     R  sum=6 (too small, expand)

[2, 3, 1, 2, 4, 3]
    ↑        ↑
    L        R  sum=10 ≥7 ✓ (size=4, shrink!)

... continue until [4,3] with size=2 ✓

Java Code

int minSubArrayLen(int target, int[] nums) {
    int left = 0;
    int sum = 0;
    int minLen = Integer.MAX_VALUE;

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

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

    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

Memory Trick

Expand when sum is too small. Shrink when sum is big enough. Always keep the smallest valid window!

🏔️ Pattern 4: Sliding Window Maximum

The Problem

Given an array and window size k, find the maximum element in each window position.

Example

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

Window positions → Maximum:
[1, 3, -1]        → 3
[3, -1, -3]       → 3
[-1, -3, 5]       → 5
[-3, 5, 3]        → 5
[5, 3, 6]         → 6
[3, 6, 7]         → 7

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

The Deque Trick

We use a deque (double-ended queue) to keep track of useful elements:

graph TD
    A["Deque stores INDICES"]
    A --> B["Front = index of current max"]
    B --> C["Always decreasing order"]
    C --> D["Remove smaller elements"]
    D --> E["Remove out-of-window elements"]

Why Deque?

Without deque: O(n × k) - check all k elements each time
With deque:    O(n)     - each element enters/exits once

Java Code

int[] maxSlidingWindow(int[] nums, int k) {
    if (nums.length == 0) return new int[0];

    int n = nums.length;
    int[] result = new int[n - k + 1];
    Deque<Integer> dq = new ArrayDeque<>();

    for (int i = 0; i < n; i++) {
        // Remove indices outside window
        while (!dq.isEmpty() && dq.peekFirst() < i - k + 1) {
            dq.pollFirst();
        }

        // Remove smaller elements (useless)
        while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) {
            dq.pollLast();
        }

        dq.offerLast(i);  // Add current index

        // Record result when window is full
        if (i >= k - 1) {
            result[i - k + 1] = nums[dq.peekFirst()];
        }
    }

    return result;
}

Visual Deque Logic

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

i=0: add 1  → deque=[0]
i=1: 3>1, remove 1, add 3 → deque=[1]
i=2: -1<3, add -1 → deque=[1,2], max=3 ✓
i=3: -3<-1, add -3 → deque=[1,2,3], max=3 ✓
i=4: 5>all, clear & add 5 → deque=[4], max=5 ✓
i=5: 3<5, add 3 → deque=[4,5], max=5 ✓
i=6: 6>3, remove 3, 6>5, remove 5, add 6 → deque=[6], max=6 ✓
i=7: 7>6, remove 6, add 7 → deque=[7], max=7 ✓

🎓 Quick Comparison

🚀 When to Use Sliding Window?

Ask yourself:

1. Contiguous subarray? → Sliding Window candidate
2. Fixed size? → Fixed Window Pattern
3. Find min/max length? → Variable Window Pattern
4. Track max/min in windows? → Deque Pattern

🧠 Golden Rules

1. Never look back unnecessarily
   → Add new, remove old in O(1)

2. Two pointers move in ONE direction
   → Left never goes past right

3. Track what matters
   → Sum, count, or max—update as you slide

4. Shrink when possible
   → For variable windows, always try to minimize

🎉 You Made It!

You now understand the four core sliding window patterns:

1. Fixed Size - The photo frame approach
2. Variable Size - The rubber band approach
3. Minimum Subarray Sum - Expand then shrink
4. Sliding Window Maximum - The clever deque

These patterns solve hundreds of interview questions. Practice them, and they’ll become second nature!

“Every master was once a beginner. Every pro was once confused. Keep sliding forward!” 🪟