Skip to main content

Sliding Window

The sliding window technique efficiently processes contiguous subarrays or substrings, often reducing time complexity from O(n²) to O(n).

Fixed size window problems​

  • Window Size K: Process all subarrays of fixed size k
  • Maximum in Window: Find maximum element in each window
  • Minimum in Window: Find minimum element in each window
  • Average in Window: Calculate average for each window

Variable size window problems​

  • Longest Subarray: Find longest subarray satisfying condition
  • Shortest Subarray: Find shortest subarray satisfying condition
  • Target Sum: Find subarray with specific sum
  • Character Count: Substring with specific character frequencies

Maximum/minimum in window​

  • Sliding Maximum: Efficiently find maximum in each window
  • Sliding Minimum: Efficiently find minimum in each window
  • Deque Approach: Using double-ended queue for optimization
  • Monotonic Queue: Maintaining monotonic property

Substring problems​

  • Longest Substring: Without repeating characters
  • Shortest Substring: Containing all characters of pattern
  • Anagram Substring: Find all anagrams of pattern in string
  • Character Frequency: Substrings with specific character counts

Longest/shortest subarray​

  • Longest Subarray: With sum ≤ target
  • Shortest Subarray: With sum ≥ target
  • Longest Subarray: With at most k distinct elements
  • Shortest Subarray: With at least k distinct elements