BeginnerArrays & Strings

Sliding Window

Maintain a window of elements and slide it across the array to find optimal subarrays

Time: O(n)
Space: O(k)
Pattern Overview

Core Idea

The sliding window pattern maintains a contiguous subset of elements (window) and efficiently slides it across the array. It can be fixed-size or variable-size, and often uses a hash map to track element frequencies within the window.

When to Use

Use when finding subarrays or substrings with specific properties, such as maximum/minimum sum, longest substring with k distinct characters, or finding all anagrams. Particularly useful when the problem asks for contiguous elements.

General Recognition Cues
General indicators that this pattern might be applicable
  • Keywords: "subarray", "substring", "contiguous"
  • Finding longest/shortest subarray with certain property
  • Maximum/minimum sum of subarray of size k
  • Finding all anagrams or permutations in a string
  • Problems with "at most k" or "exactly k" constraints
  • Maintaining running statistics over a range
Pattern Variants & Approaches
Different methodologies and implementations for this pattern
1

Fixed-Size Window

Window size remains constant as it slides across the array

When to Use This Variant
  • Problem specifies exact window size k
  • Maximum/minimum of k consecutive elements
  • Average of subarrays of size k
  • Fixed-length substring problems
  • Rolling statistics over fixed range
Use Case
Maximum sum of k consecutive elements, average of subarrays
Advantages
  • Simple to implement and understand
  • Predictable window behavior
  • Easy to track window boundaries
  • Efficient for fixed-constraint problems
Implementation
def fixed_window(arr, k):
      if len(arr) < k:
          return 0
      
      # Calculate first window
      window_sum = sum(arr[:k])
      max_sum = window_sum
      
      # Slide window
      for i in range(k, len(arr)):
          window_sum = window_sum - arr[i - k] + arr[i]
          max_sum = max(max_sum, window_sum)
      
      return max_sum
2

Variable-Size Window (Expanding/Shrinking)

Window size changes dynamically based on conditions

When to Use This Variant
  • Longest/shortest subarray with condition
  • "At most k" or "at least k" constraints
  • Find optimal window size
  • Condition-based window adjustment
  • Dynamic constraint satisfaction
Use Case
Longest substring with k distinct characters, minimum window substring
Advantages
  • Handles complex constraints
  • Adapts to problem requirements
  • Finds optimal window sizes
  • More flexible than fixed-size
Implementation
def variable_window(s, k):
      window_start = 0
      max_length = 0
      char_freq = {}
      
      for window_end in range(len(s)):
          # Expand window
          right_char = s[window_end]
          char_freq[right_char] = char_freq.get(right_char, 0) + 1
          
          # Shrink window if needed
          while len(char_freq) > k:
              left_char = s[window_start]
              char_freq[left_char] -= 1
              if char_freq[left_char] == 0:
                  del char_freq[left_char]
              window_start += 1
          
          # Update result
          max_length = max(max_length, window_end - window_start + 1)
      
      return max_length
3

Two-Pointer Window with Frequency Map

Combines sliding window with hash map for character/element tracking

When to Use This Variant
  • Finding anagrams or permutations
  • Character frequency matching
  • Pattern matching in strings
  • Substring with exact character counts
  • Need to track element occurrences
Use Case
Finding anagrams, permutation in string, character replacement
Advantages
  • Tracks element frequencies efficiently
  • Handles duplicate elements
  • O(1) window validation
  • Flexible for pattern matching
Implementation
def window_with_freq(s, pattern):
      pattern_freq = {}
      for char in pattern:
          pattern_freq[char] = pattern_freq.get(char, 0) + 1
      
      window_start = 0
      matched = 0
      result = []
      
      for window_end in range(len(s)):
          right_char = s[window_end]
          
          if right_char in pattern_freq:
              pattern_freq[right_char] -= 1
              if pattern_freq[right_char] == 0:
                  matched += 1
          
          if matched == len(pattern_freq):
              result.append(window_start)
          
          if window_end >= len(pattern) - 1:
              left_char = s[window_start]
              if left_char in pattern_freq:
                  if pattern_freq[left_char] == 0:
                      matched -= 1
                  pattern_freq[left_char] += 1
              window_start += 1
      
      return result
Common Pitfalls
Watch out for these common mistakes
  • Not properly shrinking the window when condition is violated
  • Forgetting to update frequency maps when sliding
  • Incorrect window size calculation (off-by-one errors)
  • Not handling edge cases with window size larger than array
  • Inefficient window validation (should be O(1) per slide)
Code Templates
Compare implementations across different languages
def sliding_window(s, k):
      window_start = 0
      max_length = 0
      char_frequency = {}
      
      for window_end in range(len(s)):
          # Expand window
          right_char = s[window_end]
          char_frequency[right_char] = char_frequency.get(right_char, 0) + 1
          
          # Shrink window if needed
          while len(char_frequency) > k:
              left_char = s[window_start]
              char_frequency[left_char] -= 1
              if char_frequency[left_char] == 0:
                  del char_frequency[left_char]
              window_start += 1
          
          # Update result
          max_length = max(max_length, window_end - window_start + 1)
      
      return max_length
Example Problems
Classic LeetCode problems using this pattern
Complexity Analysis
Time Complexity
O(n)

Each element is visited at most twice (once when expanding, once when shrinking).

Space Complexity
O(k)

Space depends on window size or number of distinct elements tracked (typically O(k) or O(1)).

Ready to test your knowledge?

Test your pattern recognition with interactive questions