Sliding Window

The idea

A brute-force approach to “find the best subarray” generates every possible subarray — O(n²) or O(n³). A sliding window maintains a contiguous subarray (the “window”) and slides it across the input, adjusting as needed. Because each element enters and exits the window at most once, the total work is O(n).

Two variants:

• Fixed window: size k is given. Slide one step at a time.
• Variable window: expand right until a condition breaks, then shrink from the left.

Fixed window

Problem: Maximum sum of any subarray of size k.

Brute force — O(n·k):

function maxSumBrute(nums: number[], k: number): number {
  let max = -Infinity
  for (let i = 0; i <= nums.length - k; i++) {
    let sum = 0
    for (let j = i; j < i + k; j++) sum += nums[j]
    max = Math.max(max, sum)
  }
  return max
}

Sliding window — O(n):

function maxSum(nums: number[], k: number): number {
  // Build first window
  let windowSum = 0
  for (let i = 0; i < k; i++) windowSum += nums[i]

  let max = windowSum
  // Slide: add next element, remove first element of previous window
  for (let i = k; i < nums.length; i++) {
    windowSum += nums[i] - nums[i - k]
    max = Math.max(max, windowSum)
  }
  return max
}

The key: instead of recomputing the sum of every window from scratch, subtract the element leaving and add the element entering.

Variable window

Problem: Longest substring without repeating characters.

The window expands to the right (right++). When we get a duplicate inside the window, we shrink from the left (left++) until the duplicate is gone.

function lengthOfLongestSubstring(s: string): number {
  const seen = new Map<string, number>()  // char → last seen index
  let max = 0
  let left = 0

  for (let right = 0; right < s.length; right++) {
    const c = s[right]
    // If c is inside the current window, jump left past it
    if (seen.has(c) && seen.get(c)! >= left) {
      left = seen.get(c)! + 1
    }
    seen.set(c, right)
    max = Math.max(max, right - left + 1)
  }
  return max
}

Template for variable window:

let left = 0
const windowState = new Map()  // or counter, set, etc.

for (let right = 0; right < arr.length; right++) {
  // 1. Expand: add arr[right] to window state
  windowState.add(arr[right])

  // 2. Shrink: while window violates constraint
  while (/* window invalid */) {
    windowState.remove(arr[left])
    left++
  }

  // 3. Update answer (window is now valid)
  answer = Math.max(answer, right - left + 1)
}

Another variable window: minimum subarray sum

Problem: Shortest subarray whose sum is ≥ target.

function minSubarrayLen(target: number, nums: number[]): number {
  let left = 0, sum = 0, minLen = Infinity

  for (let right = 0; right < nums.length; right++) {
    sum += nums[right]
    while (sum >= target) {
      minLen = Math.min(minLen, right - left + 1)
      sum -= nums[left]
      left++
    }
  }
  return minLen === Infinity ? 0 : minLen
}

Notice the while — we keep shrinking as long as the window is valid, to find the minimum. For “maximum valid window” problems we’d update the answer before shrinking.

When to use

Sliding window fits when the problem involves:

• Contiguous subarray or substring (key word: “subarray”, “substring”, “window”)
• An optimum value (longest, shortest, maximum, minimum)
• Some constraint on the window (sum, unique characters, no repeats)

If the problem is about non-contiguous subsequences — sliding window won’t work. Use DP instead.

Complexity

Variable window appears O(n²) at first glance because of the while inside the for. But each element is added exactly once and removed at most once — so the total operations are O(2n) = O(n).