🪟 The Magic Window: Sliding Window Patterns

The Story of the Curious Explorer

Imagine you’re a little explorer with a magic magnifying glass. This glass can only show you a small part of a treasure map at a time. As you slide it across the map, you discover hidden gems, count gold coins, or find the biggest treasure in each section.

That magnifying glass? It’s called a Sliding Window!

What is Sliding Window?

Think of a train with windows. As the train moves along the track (your array), you can only see what’s through the window at any moment.

Array: [2, 1, 5, 1, 3, 2]
       ↓ ↓ ↓
      [2, 1, 5]  ← Window sees these 3
           ↓ ↓ ↓
          [1, 5, 1]  ← Slides forward!

Why use it? Instead of checking every possible group (very slow!), we cleverly slide and update in one smooth motion.

🎯 Pattern 1: Fixed Size Sliding Window

The Story

You have a basket that holds exactly 3 apples. You walk along a row of apple trees. At each step, you pick the apple in front and drop the one behind. Your job: find when your basket had the most apples.

How It Works

1. Fill your basket with the first 3 items
2. Slide forward: Add the next item, remove the first
3. Track your answer as you go

Simple Example

Problem: Find the maximum sum of any 3 consecutive numbers.

def max_sum_fixed(arr, k):
    # Step 1: Fill the first window
    window_sum = sum(arr[:k])
    max_sum = window_sum

    # Step 2: Slide the window
    for i in range(k, len(arr)):
        # Add new element, remove old
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)

    return max_sum

# Try it!
nums = [2, 1, 5, 1, 3, 2]
print(max_sum_fixed(nums, 3))  # Output: 9

graph TD
    A["Start: Window [2,1,5] = 8"] --> B["Slide: [1,5,1] = 7"]
    B --> C["Slide: [5,1,3] = 9 ✨"]
    C --> D["Slide: [1,3,2] = 6"]
    D --> E["Answer: 9"]

Why It’s Fast

• Brute Force: Check every group → O(n × k)
• Sliding Window: Slide once → O(n)

🎯 Pattern 2: Variable Size Sliding Window

The Story

Now imagine your basket can stretch and shrink! You want the smallest basket that can hold at least 10 apples. Sometimes you grow it to collect more, sometimes you shrink it to find the smallest fit.

How It Works

1. Grow the window until you meet the goal
2. Shrink from the left while still meeting the goal
3. Track the smallest window that works

Simple Example

Problem: Find the smallest subarray with sum ≥ target.

def min_subarray_len(target, arr):
    left = 0
    current_sum = 0
    min_len = float('inf')

    for right in range(len(arr)):
        # Grow window
        current_sum += arr[right]

        # Shrink while condition met
        while current_sum >= target:
            min_len = min(min_len, right - left + 1)
            current_sum -= arr[left]
            left += 1

    return min_len if min_len != float('inf') else 0

# Try it!
nums = [2, 3, 1, 2, 4, 3]
print(min_subarray_len(7, nums))  # Output: 2

graph TD
    A["Target: 7"] --> B["[2,3,1,2] = 8 ✓ len=4"]
    B --> C["Shrink: [3,1,2] = 6 ✗"]
    C --> D["Grow: [3,1,2,4] = 10 ✓ len=4"]
    D --> E["Shrink: [1,2,4] = 7 ✓ len=3"]
    E --> F["Shrink: [2,4] = 6 ✗"]
    F --> G["Grow: [4,3] = 7 ✓ len=2 ✨"]
    G --> H["Answer: 2"]

🎯 Pattern 3: Minimum Size Subarray Sum

This is the classic variable window problem! Let’s master it.

The Challenge

Given numbers and a target, find the shortest chunk that adds up to at least the target.

Real-Life Analogy

You’re filling a water bucket (target). You have cups of different sizes (array). What’s the fewest cups needed to fill the bucket?

Complete Solution

def min_size_subarray_sum(target, nums):
    """
    Find smallest subarray with sum >= target
    Returns 0 if impossible
    """
    n = len(nums)
    left = 0
    current_sum = 0
    result = float('inf')

    for right in range(n):
        # Add right element to window
        current_sum += nums[right]

        # Try to minimize window
        while current_sum >= target:
            # Update best answer
            result = min(result, right - left + 1)
            # Remove left element
            current_sum -= nums[left]
            left += 1

    # Return 0 if no valid subarray
    return result if result != float('inf') else 0

Step-by-Step Visual

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

Step 1: [2] = 2          ❌ Need more
Step 2: [2,3] = 5        ❌ Need more
Step 3: [2,3,1] = 6      ❌ Need more
Step 4: [2,3,1,2] = 8    ✅ Found it! Length = 4
        Shrink → [3,1,2] = 6  ❌ Too small
Step 5: [3,1,2,4] = 10   ✅ Length = 4
        Shrink → [1,2,4] = 7  ✅ Length = 3
        Shrink → [2,4] = 6    ❌ Too small
Step 6: [2,4,3] = 9      ✅ Length = 3
        Shrink → [4,3] = 7    ✅ Length = 2 ✨
        Shrink → [3] = 3      ❌ Too small

Answer: 2 (subarray [4,3])

🎯 Pattern 4: Sliding Window Maximum

The Story

You’re watching a parade through a window that shows exactly k floats at a time. You want to know: what’s the tallest float you can see at each position?

The Tricky Part

This needs a special helper: a deque (double-ended queue) that keeps track of potential maximums.

Simple Example

from collections import deque

def sliding_window_max(nums, k):
    """
    Find maximum in each window of size k
    """
    result = []
    dq = deque()  # Stores indices

    for i in range(len(nums)):
        # Remove indices outside window
        while dq and dq[0] < i - k + 1:
            dq.popleft()

        # Remove smaller elements
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()

        # Add current index
        dq.append(i)

        # Record result once window is full
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

# Try it!
nums = [1, 3, -1, -3, 5, 3, 6, 7]
print(sliding_window_max(nums, 3))
# Output: [3, 3, 5, 5, 6, 7]

Visual Walkthrough

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

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

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

graph TD
    A["Deque tracks potential max"] --> B["Front = current max"]
    B --> C["Remove if outside window"]
    C --> D["Remove if smaller than new"]
    D --> E["New element joins deque"]

Why Deque?

🌟 The Big Picture

🚀 Quick Tips

1. Fixed window? → Add right, remove left
2. Variable window? → Two pointers (left & right)
3. Finding maximum? → Think deque!
4. Sum problems? → Track running total

Your Superpower

Now you have a magic window you can slide across any problem:

• Count things in groups ✓
• Find shortest/longest subarrays ✓
• Track maximums efficiently ✓

Remember: The window slides, you don’t restart. That’s the secret to speed!

graph TD
    A["See a subarray problem?"] --> B{"Fixed size?"}
    B -->|Yes| C["Fixed Window Pattern"]
    B -->|No| D{"Need shortest/longest?"}
    D -->|Yes| E["Variable Window Pattern"]
    D -->|No| F{"Track max/min in windows?"}
    F -->|Yes| G["Deque Pattern"]

You’re now a Sliding Window Master! 🎉