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.

Optimization — Index Jump (LC 3 only): When constraint is "no duplicate char", skip the while loop. Store last-seen index instead of frequency. Jump left directly.

seen = {}
left = 0
ans = 0
for right, char in enumerate(s):
    if char in seen and seen[char] >= left:
        left = seen[char] + 1   # jump, don't creep
    seen[char] = right
    ans = max(ans, right - left + 1)

Use while-loop pattern for all other variable window problems. Index-jump only when eliminating a single specific element.

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

---

Pattern 4 — Counting Subarrays (Count Valid Windows Ending at Right)

When problem asks "how many subarrays satisfy X": every time you have a valid window [left, right], there are (right - left + 1) valid subarrays ending at right (starting at left, left+1, ..., right).

def countSubarrays(arr, condition):
    left = 0
    count = 0
    state = ...

    for right in range(len(arr)):
        # expand window
        # update state with arr[right]

        while window_invalid(state):
            # shrink from left
            left += 1

        count += right - left + 1    # all subarrays [left..right], [left+1..right], ..., [right..right]

    return count

"Exactly K" pattern: Exactly K = AtMost(K) - AtMost(K-1). Direct "exactly K" is hard to shrink on; convert to "at most."

# LC 992 — Subarrays with Exactly K Distinct Integers
def subarraysWithKDistinct(nums, k):
    def atMost(k):
        count = collections.defaultdict(int)
        left = result = 0
        for right in range(len(nums)):
            count[nums[right]] += 1
            while len(count) > k:
                count[nums[left]] -= 1
                if count[nums[left]] == 0:
                    del count[nums[left]]
                left += 1
            result += right - left + 1
        return result
    return atMost(k) - atMost(k - 1)

---

Pattern 5 — Sliding Window Maximum (Monotonic Deque)

Keep deque of indices with decreasing values. Front always = current window max. O(N) total.

from collections import deque

# LC 239 — Sliding Window Maximum
def maxSlidingWindow(nums, k):
    dq = deque()   # indices, decreasing values
    result = []

    for right in range(len(nums)):
        # Remove indices out of window
        while dq and dq[0] < right - k + 1:
            dq.popleft()
        # Maintain decreasing order (pop smaller elements from back)
        while dq and nums[dq[-1]] < nums[right]:
            dq.pop()
        dq.append(right)
        # Window has k elements
        if right >= k - 1:
            result.append(nums[dq[0]])   # front = max

    return result

---

Pattern Type Summary

---

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