Sliding Window: When and How to Use It

What is the Sliding Window Pattern?

The sliding window technique is used to perform operations on a specific window size of an array or string. Instead of recalculating from scratch for each window (O(n×k) time), we "slide" the window by one position and update our calculation incrementally (O(n) time).

Think of it like sliding a physical window across a wall - as you move it, you only need to account for what enters and what leaves the window.

When to Use Sliding Window

Consider the sliding window pattern when:

• Finding subarrays or substrings that meet certain criteria
• Maximum/minimum sum of size k subarray
• Longest/shortest substring with certain properties
• Contiguous sequence problems
• Questions mention: "subarray", "substring", "consecutive elements", "window"

Two Types of Sliding Window

1. Fixed-Size Window

The window size is predetermined and constant. Slide it one position at a time.

function maxSumSubarray(arr: number[], k: number): number {
  if (arr.length < k) return -1
  
  // Calculate sum of first window
  let windowSum = 0
  for (let i = 0; i < k; i++) {
    windowSum += arr[i]
  }
  
  let maxSum = windowSum
  
  // Slide window: remove leftmost, add rightmost
  for (let i = k; i < arr.length; i++) {
    windowSum = windowSum - arr[i - k] + arr[i]
    maxSum = Math.max(maxSum, windowSum)
  }
  
  return maxSum
}

// Example: maxSumSubarray([1, 4, 2, 10, 2, 3, 1, 0, 20], 4) → 24
// Window: [10, 2, 3, 9] = 24

2. Dynamic-Size Window (Variable)

The window expands and contracts based on a condition. Use two pointers:left and right.

function longestSubstringKDistinct(s: string, k: number): number {
  const charCount = new Map<string, number>()
  let left = 0
  let maxLength = 0
  
  for (let right = 0; right < s.length; right++) {
    // Expand window: add right character
    const rightChar = s[right]
    charCount.set(rightChar, (charCount.get(rightChar) || 0) + 1)
    
    // Contract window: remove from left while invalid
    while (charCount.size > k) {
      const leftChar = s[left]
      charCount.set(leftChar, charCount.get(leftChar)! - 1)
      if (charCount.get(leftChar) === 0) {
        charCount.delete(leftChar)
      }
      left++
    }
    
    // Update result
    maxLength = Math.max(maxLength, right - left + 1)
  }
  
  return maxLength
}

// Example: longestSubstringKDistinct("araaci", 2) → 4
// Longest substring with ≤ 2 distinct chars: "araa"

The Template Pattern

Most dynamic sliding window problems follow this template:

function slidingWindowTemplate(arr: any[]): number {
  let left = 0
  let result = 0
  // Initialize window state (counter, map, sum, etc.)
  
  for (let right = 0; right < arr.length; right++) {
    // 1. Add arr[right] to window
    
    // 2. While window is invalid, shrink from left
    while (/* window condition violated */) {
      // Remove arr[left] from window
      left++
    }
    
    // 3. Update result with current valid window
    result = Math.max(result, right - left + 1)
  }
  
  return result
}

Common Problems & Solutions

Problem 1: Longest Substring Without Repeating Characters

Question: Find the length of the longest substring without repeating characters.

function lengthOfLongestSubstring(s: string): number {
  const charSet = new Set<string>()
  let left = 0
  let maxLength = 0
  
  for (let right = 0; right < s.length; right++) {
    // Shrink window until no duplicates
    while (charSet.has(s[right])) {
      charSet.delete(s[left])
      left++
    }
    
    charSet.add(s[right])
    maxLength = Math.max(maxLength, right - left + 1)
  }
  
  return maxLength
}

// Example: "abcabcbb" → 3 (substring "abc")
// Example: "bbbbb" → 1 (substring "b")

Problem 2: Minimum Window Substring

Question: Find the smallest substring in s that contains all characters from t.

function minWindow(s: string, t: string): string {
  if (s.length === 0 || t.length === 0) return ""
  
  // Count characters needed
  const need = new Map<string, number>()
  for (const char of t) {
    need.set(char, (need.get(char) || 0) + 1)
  }
  
  let left = 0
  let right = 0
  let formed = 0 // Unique chars in window matching need
  const required = need.size
  const windowCounts = new Map<string, number>()
  
  // [minLen, left, right]
  let ans: [number, number, number] = [Infinity, 0, 0]
  
  while (right < s.length) {
    // Expand window
    const char = s[right]
    windowCounts.set(char, (windowCounts.get(char) || 0) + 1)
    
    if (need.has(char) && windowCounts.get(char) === need.get(char)) {
      formed++
    }
    
    // Contract window while valid
    while (formed === required && left <= right) {
      // Update result
      if (right - left + 1 < ans[0]) {
        ans = [right - left + 1, left, right]
      }
      
      // Shrink from left
      const leftChar = s[left]
      windowCounts.set(leftChar, windowCounts.get(leftChar)! - 1)
      
      if (need.has(leftChar) && 
          windowCounts.get(leftChar)! < need.get(leftChar)!) {
        formed--
      }
      
      left++
    }
    
    right++
  }
  
  return ans[0] === Infinity ? "" : s.substring(ans[1], ans[2] + 1)
}

// Example: s = "ADOBECODEBANC", t = "ABC" → "BANC"

Problem 3: Maximum Average Subarray

Question: Find the contiguous subarray of length k with maximum average.

function findMaxAverage(nums: number[], k: number): number {
  // Calculate first window
  let sum = 0
  for (let i = 0; i < k; i++) {
    sum += nums[i]
  }
  
  let maxSum = sum
  
  // Slide window
  for (let i = k; i < nums.length; i++) {
    sum = sum - nums[i - k] + nums[i]
    maxSum = Math.max(maxSum, sum)
  }
  
  return maxSum / k
}

// Example: [1,12,-5,-6,50,3], k=4 → 12.75
// Subarray: [12,-5,-6,50]

Time & Space Complexity

Fixed Window:
Time: O(n) - Single pass through array
Space: O(1) - Only storing window sum/state

Dynamic Window:
Time: O(n) - Each element visited at most twice (right pointer adds, left pointer removes)
Space: O(k) - Where k is the size of character set or window tracking structure

Pro Tips

• Right pointer always moves forward - Never goes backwards
• Left pointer catches up - Only moves when window is invalid
• Use hash map for character/element frequency tracking
• Check edge cases: Empty array, k larger than array length, k=1
• Update result after checking validity - Not during shrinking

Common Mistakes

• Moving both pointers in nested loops → O(n²) time
• Forgetting to remove left element when shrinking window
• Updating result before window is valid
• Using wrong loop condition (should be right < n)

Practice Problems

Test your understanding with these problems:

• Easy: Maximum Average Subarray, Contains Duplicate II
• Medium: Longest Substring Without Repeating Characters, Max Consecutive Ones III, Fruit Into Baskets
• Hard: Minimum Window Substring, Sliding Window Maximum

Continue Learning

• Two Pointers Pattern Explained - A related technique often used together with sliding window
• Hash Maps: When and Why - Essential for tracking window contents efficiently
• Big O Notation Explained - Understand the O(n) complexity of sliding window
• Start Practicing - Apply sliding window to real interview problems