The Sliding Window Technique

If a problem asks for the longest or shortest contiguous run that satisfies something, it is a sliding window. That single recognition saves more time than any other pattern here.

The idea

Keep a start and an end index. Extend the end to grow the window. When the window breaks the rule, move the start until it is valid again. Each index moves forward at most once, so the whole scan is O(n) even though it looks like a nested loop.

Fixed window

When the size is given, slide it and adjust by one at each step.

function maxSumOfK(nums, k) {
  let sum = 0
  for (let i = 0; i < k; i++) sum += nums[i]

  let best = sum

  for (let i = k; i < nums.length; i++) {
    // Add the new element, drop the one that left.
    sum += nums[i] - nums[i - k]
    best = Math.max(best, sum)
  }

  return best
}

console.log(maxSumOfK([2, 1, 5, 1, 3, 2], 3))  // 9

Recomputing the sum for every window would be O(n × k). Adding one and subtracting one makes it O(n).

Variable window

When the size depends on a condition, grow and shrink as needed.

function shortestRunAtLeast(nums, target) {
  let start = 0
  let sum = 0
  let best = Infinity

  for (let end = 0; end < nums.length; end++) {
    sum += nums[end]

    // Valid — try to make it smaller.
    while (sum >= target) {
      best = Math.min(best, end - start + 1)
      sum -= nums[start]
      start++
    }
  }

  return best === Infinity ? 0 : best
}

console.log(shortestRunAtLeast([2, 3, 1, 2, 4, 3], 7))  // 2

The inner while looks like it makes this quadratic. It does not - start only ever increases, so across the whole run it moves at most n times.

With a map, for character problems

function longestWithKDistinct(s, k) {
  const counts = new Map()
  let start = 0
  let best = 0

  for (let end = 0; end < s.length; end++) {
    const ch = s[end]
    counts.set(ch, (counts.get(ch) || 0) + 1)

    while (counts.size > k) {
      const out = s[start]
      counts.set(out, counts.get(out) - 1)
      if (counts.get(out) === 0) counts.delete(out)
      start++
    }

    best = Math.max(best, end - start + 1)
  }

  return best
}

console.log(longestWithKDistinct("eceba", 2))  // 3

The one thing that breaks it

Sliding window assumes that shrinking the window can only help. With negative numbers that assumption fails - adding an element can make a sum smaller, so a window that was invalid might become valid again later. For subarray-sum problems with negatives, use a prefix sum and a hash map instead.

Fixed versus variable windows

There are two shapes, and mixing them up is the usual source of confusion. A fixed window has a known size k: add the incoming element, remove the outgoing one, and the window never changes length. A variable window grows until a condition breaks, then shrinks from the left until it holds again.

function maxSumOfK(items, k) {
  if (items.length < k) return null

  let sum = 0
  for (let i = 0; i < k; i++) sum += items[i]

  let best = sum
  for (let i = k; i < items.length; i++) {
    sum += items[i] - items[i - k]   // add one, drop one
    best = Math.max(best, sum)
  }

  return best
}

console.log(maxSumOfK([2, 1, 5, 1, 3, 2], 3))  // 9

When it does not apply

A sliding window needs the answer to change predictably as the window moves. That holds for sums and counts of positive numbers, and for "contains at most k distinct" style conditions.

It breaks the moment negative numbers enter a sum problem: shrinking the window can now increase the total, so the window no longer has a direction to move. That case is a prefix-sum-with-a-hash-map problem instead, which is why those two topics are so often confused in interviews.