Sliding Window

Max sum subarray of size K

Slide a fixed-size window across the array. Instead of summing all K elements each time, subtract the element leaving the window and add the one entering.

Longest substring without repeats

A variable window. Expand the right edge one character at a time. If the new character is already in the window, shrink from the left until it's not.

Templates

Fixed window

function fixedWindow(arr: number[], k: number) {
  let sum = 0
  for (let i = 0; i < k; i++) sum += arr[i]
  let max = sum

  for (let i = k; i < arr.length; i++) {
    sum += arr[i] - arr[i - k]
    max = Math.max(max, sum)
  }
  return max
}

Variable window

function variableWindow(s: string) {
  const seen = new Set<string>()
  let left = 0, longest = 0

  for (let r = 0; r < s.length; r++) {
    while (seen.has(s[r])) {
      seen.delete(s[left])
      left++
    }
    seen.add(s[r])
    longest = Math.max(longest, r - left + 1)
  }
  return longest
}