Sliding Window Pattern: Fixed & Dynamic Window Mastery

When solving contiguous subarray or substring problems, the brute-force approach of evaluating every start and end index requires generating O(N^2) combinations. For each window, recalculating aggregate properties (like sums, distinct character counts, or frequency hashes) pushes runtime to O(N^3) or O(N^2).

The Sliding Window Pattern optimizes this to an optimal amortized O(N) by maintaining a running state across a moving window. Instead of recomputing from scratch, you incrementally add the element entering from the right and subtract the element leaving from the left.

Fixed vs. Dynamic Sliding Windows

flowchart TD
    Start(["Start: left = 0, right = 0"]) --> Expand["1. Expand Right:\nInclude arr[right] in running state"]
    Expand --> TypeCheck{"Window Type?"}
    
    TypeCheck -->|Fixed Size K| FixedCheck{"right - left + 1 == k ?"}
    FixedCheck -->|No| AdvanceRight["right++"]
    FixedCheck -->|Yes| RecordFixed["Record answer\nSubtract arr[left]\nleft++"]
    RecordFixed --> AdvanceRight

    TypeCheck -->|Dynamic / Variable| ValidCheck{"Is Window Valid?"}
    ValidCheck -->|Invalid State| Shrink["Shrink Window:\nSubtract arr[left]\nleft++"]
    Shrink --> ValidCheck
    ValidCheck -->|Valid State| RecordDynamic["Update Best Answer (min/max length)\nright++"]
    RecordDynamic --> AdvanceRight

    AdvanceRight --> Terminate{"right < length ?"}
    Terminate -->|Yes| Expand
    Terminate -->|No| Finish(["Return Result"])

Pattern 1: Fixed-Size Window (Maximum Sum Subarray of Size K)

For a fixed window of size K, the window boundary conditions are straightforward: once the right pointer hits index k - 1, slide left simultaneously with right.

Java Implementation

public class FixedSlidingWindow {
    public static int maxSubarraySum(int[] nums, int k) {
        if (nums == null || nums.length < k || k <= 0) return 0;

        int windowSum = 0;
        int maxSum = Integer.MIN_VALUE;
        int left = 0;

        for (int right = 0; right < nums.length; right++) {
            windowSum += nums[right]; // Add incoming element

            // Once we have accumulated k elements, slide the window
            if (right >= k - 1) {
                maxSum = Math.max(maxSum, windowSum);
                windowSum -= nums[left]; // Remove outgoing element
                left++;                 // Slide window forward
            }
        }

        return maxSum;
    }
}

Pattern 2: Dynamic Window (Longest Substring Without Repeating Characters)

In variable-size windows, the window expands by advancing right. Whenever the state becomes invalid (e.g., a duplicate character is introduced), left contracts the window until the invariant is restored.

Why is this O(N) and not O(N^2)? Even though there is a nested while loop inside the for loop, the left pointer moves forward at most N times across the entire algorithm execution. Therefore, each element is visited at most twice.

Python Implementation

def length_of_longest_substring(s: str) -> int:
    """Finds length of longest substring without repeating characters in O(N)."""
    char_index_map = {}
    max_len = 0
    left = 0

    for right, char in enumerate(s):
        # If char was seen within current window, jump left past its previous position
        if char in char_index_map and char_index_map[char] >= left:
            left = char_index_map[char] + 1

        char_index_map[char] = right
        max_len = max(max_len, right - left + 1)

    return max_len

# Example
text = "abcabcbb"
print(length_of_longest_substring(text)) # Output: 3 ("abc")

Pattern 3: Minimum Window Substring (Complex Constraints)

Given strings s and t, find the minimum window in s containing all characters of t.

1. Count character requirements of target string t in a hash table.
2. Expand right across s, decrementing needed character frequencies.
3. When all requirements are satisfied (matched == target_count), greedily advance left to find the smallest valid window before breaking the match constraint.

TypeScript Implementation

export function minWindow(s: string, t: string): string {
  if (!s || !t || s.length < t.length) return "";

  const required = new Map();
  for (const char of t) {
    required.set(char, (required.get(char) || 0) + 1);
  }

  const windowCounts = new Map();
  let left = 0;
  let matchCount = 0;
  let minLen = Infinity;
  let startIndex = 0;

  for (let right = 0; right < s.length; right++) {
    const char = s[right];
    windowCounts.set(char, (windowCounts.get(char) || 0) + 1);

    if (required.has(char) && windowCounts.get(char) === required.get(char)) {
      matchCount++;
    }

    // Shrink window from the left while it remains valid
    while (matchCount === required.size) {
      const currentLen = right - left + 1;
      if (currentLen < minLen) {
        minLen = currentLen;
        startIndex = left;
      }

      const leftChar = s[left];
      windowCounts.set(leftChar, windowCounts.get(leftChar)! - 1);
      if (required.has(leftChar) && windowCounts.get(leftChar)! < required.get(leftChar)!) {
        matchCount--;
      }
      left++;
    }
  }

  return minLen === Infinity ? "" : s.substring(startIndex, startIndex + minLen);
}

Common Pitfalls & Checklist

• Boundary Verification: For fixed windows of size K, always confirm if K > length, returning empty or zero immediately.
• Hash Map Optimization: When dealing with ASCII strings, replace generic hash maps with a fixed int[128] or int[256] array to eliminate heap allocations and drastically improve memory cache locality.
• State Invalidation: Double check whether the question asks for maximum or minimum window length. Maximum length problems record the result during expansion; minimum length problems record during contraction.

Complexity Matrix