Pattern · Sliding Window

Two pointers, one window. Grow it, shrink it, never look back.

Every window problem fits one of four molds. Recognize which, then run the loop — the rest is bookkeeping.

① Fixed-Size Window

Common

What This Is

You slide a window of constant size k across the array. Examples: max in each k-size window, sum of k consecutive elements, character frequency in a k-char substring.

When to Use

When the problem asks for "every k", "consecutive k elements", or "k-size window". Window size is fixed; you just slide it.

The Pattern

1. Build the initial window of size k
2. Slide right: add new element, remove leftmost
3. Process the window (max, sum, etc.) at each step
4. Left pointer moves automatically (always k positions behind right)

Fixed-size window template (Python)
fixed_size_window
def maxSumSubarray(arr, k):
    # Build initial window: sum of first k elements
    current_sum = sum(arr[:k])
    max_sum = current_sum
    left = 0

    for right in range(k, len(arr)):
        # Add new element on right
        current_sum += arr[right]
        # Remove leftmost element (window slides)
        current_sum -= arr[left]
        left += 1
        # Update answer with current window
        max_sum = max(max_sum, current_sum)

    return max_sum

Interview Tips

  • Recognize: "for every k consecutive elements", "each window of size k"
  • Setup: Use an array, hashmap, or deque to track data in the window
  • Avoid: Re-computing from scratch for each window (O(n*k)) — use sliding (O(n))
  • Edge case: If k > arr.length, return empty

② Variable-Size Window (Expanding)

Core

What This Is

Expand the window until a condition is met (e.g., "sum ≥ target", "all unique chars"). Track the max/min window size that satisfies the condition.

When to Use

When the problem asks for "longest", "shortest", or "find such that condition holds". Condition can be checked incrementally as you expand.

The Pattern

1. Right pointer expands freely
2. When condition is met, record/update result
3. Left pointer shrinks to optimize (find tighter bound)
4. Repeat: expand right, shrink left

Expanding window template (Python)
expanding_window
def lengthOfLongestSubstring(s):
    char_set = set()
    left = 0
    max_length = 0

    for right in range(len(s)):
        # Add character at right to window
        while s[right] in char_set:
            # Shrink left until duplicate is gone
            char_set.remove(s[left])
            left += 1
        # Add the current character
        char_set.add(s[right])
        # Update answer: track longest substring
        max_length = max(max_length, right - left + 1)

    return max_length

Interview Tips

  • Recognize: "longest substring", "shortest subarray", "find such that"
  • Setup: Left and right pointers. Track a condition incrementally.
  • Key: Shrink left to find the tightest bound. Record result during shrinking.
  • Complexity: Each element enters and exits the window once → O(n)

③ Variable-Size Window (Contracting)

Advanced

What This Is

Expand the window until a condition is met, then shrink to find the tightest valid window. Common in problems like "minimum window substring" or "smallest range".

When to Use

When you need to find the smallest substring/subarray that contains or satisfies something. Expand to capture, then contract to minimize.

The Pattern

1. Right pointer expands until condition is satisfied
2. Left pointer shrinks while condition still holds
3. Record the window at each valid state
4. Continue expanding right

Contracting window template (Python)
contracting_window
def minWindow(s, t):
    if not s or not t:
        return ""
    req_count = {}
    for c in t:
        req_count[c] = req_count.get(c, 0) + 1

    formed = 0
    window_count = {}
    left = 0
    result = (float("inf"), None, None)

    for right in range(len(s)):
        # Add character at right to window
        window_count[s[right]] = window_count.get(s[right], 0) + 1
        if s[right] in req_count and window_count[s[right]] == req_count[s[right]]:
            formed += 1

        # Shrink window while it has all required chars
        while left <= right and formed == len(req_count):
            # Record smallest valid window
            if right - left + 1 < result[0]:
                result = (right - left + 1, left, right)
            # Remove character at left
            window_count[s[left]] -= 1
            if s[left] in req_count and window_count[s[left]] < req_count[s[left]]:
                formed -= 1
            left += 1

    return "" if result[0] == float("inf") else s[result[1]:result[2] + 1]

Interview Tips

  • Recognize: "minimum window", "smallest range", "shortest subarray that contains"
  • Condition check: Use a "formed" counter or frequency map to know when condition is met
  • Shrinking: Only shrink while condition holds. Once it breaks, expand right again.
  • Result: Update during shrinking (you're finding the tightest window at each stage)

④ Min/Max Tracking (Degenerate Window)

Edge Case

What This Is

A "window" that collapses to tracking just the running min/max (or best state seen so far). Examples: "best time to buy stock", "max profit".

When to Use

When you only care about comparing the current element with the best prior element. The window is implicitly [0...i], but you only track the relevant prior state.

The Pattern

1. Iterate through the array
2. Track the running min/max (or best prior state)
3. At each step, compute result using current element and the tracked best
4. Update the tracked best

Min tracking template (Python)
min_tracking
def maxProfit(prices):
    if not prices:
        return 0
    min_price = prices[0]
    max_profit = 0

    for price in prices[1:]:
        # Calculate profit if we sell at current price
        profit = price - min_price
        # Update max profit seen so far
        max_profit = max(max_profit, profit)
        # Update minimum price seen so far
        min_price = min(min_price, price)

    return max_profit

Interview Tips

  • Recognize: "best time", "max profit", "single pass", comparing current to all prior
  • Setup: Track the relevant prior state (min, max, best index, etc.)
  • Process: For each element, compare with tracked state, then update state
  • Space: O(1) — just tracking a single state variable

Which Pattern Should I Use?

Is the window size fixed?
├─ YES → Pattern ①: Fixed-Size Window
└─ NO → Is the condition something you expand to find?
    ├─ YES (e.g., "all unique chars", "sum ≥ target") → Pattern ②: Expanding Window
    └─ NO (e.g., "find the minimum window that contains all") → Pattern ③: Contracting Window

Special: Only comparing current to running best (no real window)?
└─ YES → Pattern ④: Min/Max Tracking