Sliding Window

Interactive Visualization

Time Complexity

Key Points

• Fixed-size window: window size is given (e.g., max sum of k consecutive elements); slide by adding the new element and removing the oldest
• Variable-size window: window grows until a condition breaks, then shrinks from the left until the condition is restored
• Shrinking condition: clearly define when the window becomes invalid (e.g., sum exceeds target, duplicate found, too many distinct chars)
• Closely related to two pointers: the left and right boundaries of the window act as two pointers moving in the same direction
• Achieves O(n) time because each element is added and removed from the window at most once
• Common data structures inside the window: hash map for character counts, variable for running sum, set for uniqueness
• Applicable to strings (substrings) and arrays (subarrays) — any problem asking about contiguous sequences

Code Examples

function maxSumSubarray(arr, k) {
  if (arr.length < k) return null

  // Build the first window
  let windowSum = 0
  for (let i = 0; i < k; i++) {
    windowSum += arr[i]
  }

  let maxSum = windowSum

  // Slide the window: add right, remove left
  for (let i = k; i < arr.length; i++) {
    windowSum += arr[i] - arr[i - k]
    maxSum = Math.max(maxSum, windowSum)
  }

  return maxSum
}

maxSumSubarray([2, 1, 5, 1, 3, 2], 3) // 9 (5+1+3)

// Brute force: O(n*k) — recalculate sum for each position
// Sliding window: O(n) — just add one, remove one

function lengthOfLongestSubstring(s) {
  const charIndex = new Map()
  let maxLen = 0
  let left = 0

  for (let right = 0; right < s.length; right++) {
    const char = s[right]

    // If char was seen and is inside current window, shrink
    if (charIndex.has(char) && charIndex.get(char) >= left) {
      left = charIndex.get(char) + 1
    }

    charIndex.set(char, right)
    maxLen = Math.max(maxLen, right - left + 1)
  }

  return maxLen
}

lengthOfLongestSubstring('abcabcbb') // 3 ('abc')
lengthOfLongestSubstring('bbbbb')    // 1 ('b')
lengthOfLongestSubstring('pwwkew')   // 3 ('wke')

// Time: O(n), Space: O(min(n, alphabet size))

function minWindow(s, t) {
  const need = new Map()
  for (const c of t) need.set(c, (need.get(c) || 0) + 1)

  let have = 0
  const required = need.size
  let left = 0
  let minLen = Infinity
  let minStart = 0
  const windowCounts = new Map()

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

    if (need.has(c) && windowCounts.get(c) === need.get(c)) {
      have++
    }

    // Shrink window while all characters are satisfied
    while (have === required) {
      if (right - left + 1 < minLen) {
        minLen = right - left + 1
        minStart = left
      }

      const leftChar = s[left]
      windowCounts.set(leftChar, windowCounts.get(leftChar) - 1)
      if (need.has(leftChar) &&
          windowCounts.get(leftChar) < need.get(leftChar)) {
        have--
      }
      left++
    }
  }

  return minLen === Infinity ? '' : s.slice(minStart, minStart + minLen)
}

minWindow('ADOBECODEBANC', 'ABC') // 'BANC'

// Time: O(n + m), Space: O(n + m)

Common Mistakes

• Forgetting to shrink the window when the constraint is violated, leading to incorrect or oversized results
• Off-by-one errors when calculating window size (right - left + 1, not right - left)
• Not handling edge cases: empty input, k larger than array length, or no valid window existing
• Resetting the window sum or count map from scratch instead of incrementally updating, which defeats the O(n) purpose
• Confusing fixed-size and variable-size window approaches — using the wrong template for the problem type

Interview Tips

• When you see "contiguous subarray" or "substring" with an optimization goal, think sliding window
• Ask yourself: is the window size fixed or variable? This determines your template
• For variable-size windows, clearly state your expand condition and your shrink condition
• Sliding window problems often pair with a hash map for tracking element frequency inside the window
• Practice translating the brute-force O(n*k) or O(n^2) approach into the O(n) window approach step by step

Practice Problems

Related Concepts