Sliding Window Technique

TL;DR

• Bottom line: The sliding window technique processes contiguous subarrays/substrings in O(n) by maintaining two pointers (left, right) that define a window and moving them forward while updating state incrementally.
• Key tool: left/right pointers with expand/shrink logic — expand right to grow the window, shrink left when the window violates the constraint.
• Watch out for: Using nested loops (O(n²)) for problems that have a contiguous-subarray structure — sliding window reduces this to O(n).
• Works with: Any language. Arrays, strings, and any indexed sequential data. No library dependencies.

Constraints

• Input must be sequential (array/string) — sliding window does not apply to trees or graphs
• The expand/shrink condition must be monotonic for variable-size windows — if adding an element breaks validity, all larger windows containing it also break it
• Window pointers must only move forward — never reset left to 0 or decrement right mid-iteration
• State (sum, count, hash map) must be updated incrementally — recalculating from scratch defeats O(n)

Quick Reference

Decision Tree

START
├── Is the problem about a contiguous subarray or substring?
│   ├── NO → Not a sliding window problem. Consider two pointers, DP, or binary search.
│   └── YES ↓
├── Is the window size given (fixed k)?
│   ├── YES → Use FIXED-SIZE window template
│   │   ├── Need max/min of window elements? → Use monotonic deque (O(n))
│   │   └── Need sum/count/frequency? → Use running sum + hash map
│   └── NO → Variable-size window ↓
├── Are you looking for the SMALLEST valid window?
│   ├── YES → Use VARIABLE SHRINK template
│   │   └── Expand right until valid, then shrink left to find minimum
│   └── NO ↓
├── Are you looking for the LONGEST valid window?
│   ├── YES → Use VARIABLE EXPAND template
│   │   └── Expand right, shrink left only when invalid, track max length
│   └── NO ↓
└── Counting valid subarrays?
    └── YES → Use "at most K" trick: count(exactly K) = count(at most K) - count(at most K-1)

Step-by-Step Guide

1. Identify the window type

Determine whether the problem specifies a fixed window size k or requires you to find an optimal (minimum/maximum) window. If the problem says "subarray of size k" or "every k consecutive elements," use the fixed template. If it says "smallest subarray such that..." or "longest substring where...," use the variable template. [src1]

2. Initialize the window state

Set up tracking variables: left = 0, running sum/counter/hash map, and result variable. For hash map problems, use collections.Counter (Python), Map (JavaScript), or HashMap (Java). [src3]

left = 0
window_state = {}  # or: current_sum = 0
result = float('inf')  # for minimum; use float('-inf') or 0 for maximum

3. Expand the window (move right pointer)

Iterate right from 0 to len(arr)-1. On each step, add arr[right] to the window state. For sum problems: current_sum += arr[right]. For frequency problems: window_state[arr[right]] += 1. [src2]

4. Shrink the window (move left pointer)

For fixed windows: shrink when right - left + 1 > k. For variable windows: shrink while the window is invalid (shrink template) or while the window violates the constraint (expand template). On each shrink, remove arr[left] from state and increment left. [src3]

5. Update the result

After adjusting the window, check if the current window is a candidate for the answer. For minimum problems, update when the window becomes valid. For maximum problems, update on every step. [src4]

Verify: Run through a small example manually — the left pointer should never exceed right, and both should reach the end exactly once, confirming O(n).

Code Examples

Python: Maximum Sum Subarray of Size k (Fixed Window)

# Input:  arr = [2, 1, 5, 1, 3, 2], k = 3
# Output: 9 (subarray [5, 1, 3])

def max_sum_subarray(arr, k):
    n = len(arr)
    if n < k:
        return -1

    window_sum = sum(arr[:k])  # first window
    max_sum = window_sum

    for right in range(k, n):
        window_sum += arr[right] - arr[right - k]  # slide: add new, remove old
        max_sum = max(max_sum, window_sum)

    return max_sum

Python: Minimum Window Substring (Variable Shrink)

# Input:  s = "ADOBECODEBANC", t = "ABC"
# Output: "BANC"

from collections import Counter

def min_window(s, t):
    need = Counter(t)
    missing = len(t)  # chars still needed
    left = 0
    best = (0, float('inf'))  # (start, end)

    for right, char in enumerate(s):
        if need[char] > 0:
            missing -= 1
        need[char] -= 1

        while missing == 0:  # window is valid — try to shrink
            if right - left < best[1] - best[0]:
                best = (left, right)
            need[s[left]] += 1
            if need[s[left]] > 0:
                missing += 1
            left += 1

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

JavaScript: Longest Substring Without Repeating Characters (Variable Expand)

// Input:  s = "abcabcbb"
// Output: 3 (substring "abc")

function lengthOfLongestSubstring(s) {
  const seen = new Map(); // char -> last index
  let left = 0;
  let maxLen = 0;

  for (let right = 0; right < s.length; right++) {
    if (seen.has(s[right]) && seen.get(s[right]) >= left) {
      left = seen.get(s[right]) + 1; // shrink past duplicate
    }
    seen.set(s[right], right);
    maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;
}

Java: Max Consecutive Ones III (Variable Expand with Flip Budget)

// Input:  nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
// Output: 6 (flip two 0s to get [1,1,1,0,0,1,1,1,1,1,1])

public int longestOnes(int[] nums, int k) {
    int left = 0, zeros = 0, maxLen = 0;

    for (int right = 0; right < nums.length; right++) {
        if (nums[right] == 0) zeros++;

        while (zeros > k) {        // too many flips — shrink
            if (nums[left] == 0) zeros--;
            left++;
        }
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

Anti-Patterns

Wrong: Using nested loops for contiguous subarray problems

# BAD — O(n^2) brute force for max sum subarray of size k
def max_sum_brute(arr, k):
    max_sum = 0
    for i in range(len(arr) - k + 1):
        current = sum(arr[i:i+k])  # recalculates entire window each time
        max_sum = max(max_sum, current)
    return max_sum

Correct: Slide the window incrementally

# GOOD — O(n) sliding window
def max_sum_slide(arr, k):
    window_sum = sum(arr[:k])
    max_sum = window_sum
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]  # O(1) update
        max_sum = max(max_sum, window_sum)
    return max_sum

Wrong: Not updating state when shrinking the window

# BAD — shrinks left pointer but forgets to remove element from hash map
def longest_unique_bad(s):
    seen = set()
    left = 0
    max_len = 0
    for right in range(len(s)):
        seen.add(s[right])
        while s[right] in seen and len(seen) > right - left + 1:
            left += 1  # moves left but never removes s[left] from seen!
        max_len = max(max_len, right - left + 1)
    return max_len

Correct: Remove outgoing element from state on every shrink

# GOOD — properly maintains the set
def longest_unique_good(s):
    seen = set()
    left = 0
    max_len = 0
    for right in range(len(s)):
        while s[right] in seen:
            seen.remove(s[left])  # remove before moving left
            left += 1
        seen.add(s[right])
        max_len = max(max_len, right - left + 1)
    return max_len

Wrong: Resetting left pointer to 0 on each mismatch

# BAD — resets left to 0, destroying O(n) guarantee
def min_subarray_bad(arr, target):
    for right in range(len(arr)):
        left = 0  # WRONG: restarts from beginning every time
        while left <= right and sum(arr[left:right+1]) >= target:
            left += 1
    # This is O(n^2) despite looking like sliding window

Correct: Left pointer only moves forward

# GOOD — left only advances, never resets
def min_subarray_good(arr, target):
    left = 0
    current_sum = 0
    min_len = float('inf')
    for right in range(len(arr)):
        current_sum += arr[right]
        while current_sum >= target:
            min_len = min(min_len, right - left + 1)
            current_sum -= arr[left]
            left += 1  # only moves forward
    return min_len if min_len != float('inf') else 0

Common Pitfalls

• Off-by-one in window size: Window size is right - left + 1, not right - left. Using the wrong formula gives windows of size k-1. Fix: always use right - left + 1 for inclusive bounds. [src1]
• Forgetting to handle empty input: If len(arr) < k or len(s) == 0, the function should return 0 or -1 immediately. Fix: add a guard clause at the start. [src5]
• Using while vs if for shrinking: For "find minimum" problems, use while (shrink as much as possible). Mixing them up gives wrong results. Fix: use while for shrink-to-minimum, while for shrink-when-invalid. [src3]
• HashMap values going negative: When tracking character frequencies, decrementing below 0 is fine (surplus), but when checking "all matched," only count transitions from 1 to 0. Fix: track a separate matched counter. [src2]
• Not handling duplicate characters: When shrinking past a character appearing multiple times, only mark it "missing" when count goes above 0. Fix: check need[char] > 0 after incrementing. [src3]
• Assuming monotonicity with negative numbers: If the array has negative numbers and you want exact/minimum sum, sliding window alone fails. Fix: use prefix sums + hash map. [src4]

When to Use / When Not to Use

Important Caveats

• Sliding window is a specialization of the two-pointer technique — every sliding window uses two pointers, but not every two-pointer problem is a sliding window (converging pointers on sorted arrays are two-pointer, not sliding window)
• For "count subarrays with exactly K distinct elements," you cannot directly use sliding window — use the identity exactly(K) = atMost(K) - atMost(K-1) with two sliding window passes
• The O(n) time complexity assumes O(1) state updates; if your state update involves sorting or scanning the window, total complexity may be O(n log k) or O(nk) — use a monotonic deque or balanced BST for O(n) or O(n log k) min/max queries
• When elements can be negative, the monotonic property breaks for sum-based problems — current_sum ≥ target does not imply current_sum + next ≥ target, so the shrink step may skip valid windows