Sliding Window

Spot It Fast

Answer YES to all 3 → use Sliding Window:

1. Input is an Array or String?
2. Problem asks for a Subarray or Substring?
3. Looking for Longest / Shortest / Max Sum / specific count?

---

Decision Tree

Is window size K fixed?
├── Yes → Pattern 1: Fixed Window
└── No  → Pattern 2: Variable Window
    ├── "Longest" → shrink when INVALID
    └── "Shortest" → shrink when VALID, record before shrinking

Is it a pair/index relationship (buy/sell, profit)?
└── Yes → Pattern 3: Two Pointer

---

Pattern 1 — Fixed Window

Window size k is given. Add right element, drop left element every step.

def fixed_window(arr, k):
    window_sum = sum(arr[:k])
    result = window_sum

    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]   # add right, drop left
        result = max(result, window_sum)

    return result

Problems: Max Sum Subarray of Size K, Find All Anagrams (#438)

---

Pattern 2 — Variable Window

Window grows right, shrinks left only when condition breaks.

def variable_window(arr):
    left = 0
    result = 0
    state = {}

    for right in range(len(arr)):
        # 1. Expand: add arr[right]
        state[arr[right]] = state.get(arr[right], 0) + 1

        # 2. Shrink: while window is invalid, move left
        while window_is_invalid(state):
            state[arr[left]] -= 1
            if state[arr[left]] == 0:
                del state[arr[left]]
            left += 1

        # 3. Record (window is valid here)
        result = max(result, right - left + 1)

    return result

For Shortest window: record result inside the shrink loop, not after.

Problems: LC 3, LC 76, LC 424, LC 1004

---

Pattern 3 — Two Pointer

One pointer is the "anchor" (e.g. buy day), the other scans forward.

def two_pointer(prices):
    left = 0
    result = 0

    for right in range(1, len(prices)):
        if prices[right] < prices[left]:
            left = right              # cheaper buy day found, reset
        else:
            result = max(result, prices[right] - prices[left])

    return result

Problems: LC 121

---

Senior Tricks

"At Most K" trick — when problem says "exactly K distinct", it's hard to count directly. Use: atMost(K) - atMost(K-1) → LC 992

Monotonic Deque — for Sliding Window Maximum. Keep a deque of indices with decreasing values → O(1) max per window → LC 239

Two-String Window — for comparing two strings (LC 76, LC 567). Build a frequency map of the target. Expand on source. Track matchCount — when it equals distinct chars in target, window is valid.

---

Interview Opener

"I'll use a sliding window to reduce the O(N²) brute force to O(N) — right pointer expands, left pointer shrinks only when the constraint breaks."

---

Must-Master Problems