Sliding window

The insight: don't recompute, adjust

A brute-force "every contiguous subarray/substring" solution recomputes each window from scratch — O(n) work, done for O(n) windows, is O(n²). Sliding window notices that consecutive windows overlap almost entirely: moving from [i, j] to [i+1, j+1] only removes one element and adds one element. Update the running answer instead of rebuilding it, and the whole scan collapses to O(n).

Fixed-size window

// max sum of any window of size k — O(n) time, O(1) space
function maxSumWindow(nums, k) {
  let windowSum = 0;
  for (let i = 0; i < k; i++) windowSum += nums[i]; // build first window

  let best = windowSum;
  for (let i = k; i < nums.length; i++) {
    windowSum += nums[i] - nums[i - k]; // add new, drop old — O(1)
    best = Math.max(best, windowSum);
  }
  return best;
}

Variable-size window — the more common interview shape

Here the window grows on the right and shrinks from the left based on a condition, instead of staying a fixed size. This is the pattern behind "longest substring without repeating characters," "smallest subarray with sum ≥ target," and most "longest/shortest X satisfying Y" questions.

// longest substring with no repeated characters — O(n) time, O(min(n, alphabet)) space
function longestUniqueSubstring(s) {
  const lastSeen = new Map(); // char → most recent index
  let left = 0, best = 0;

  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    if (lastSeen.has(c) && lastSeen.get(c) >= left) {
      left = lastSeen.get(c) + 1; // jump left past the repeat
    }
    lastSeen.set(c, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

Notice left only ever moves forward — it never resets to 0 and re-scans. That "each pointer visits each index at most once" property is why this is O(n) and not O(n²) despite looking like a nested loop conceptually.

Watch the window grow and jump, step by step

s = "abcabcbb":

left jumps straight to one past the repeat's last position — never one step at a time, never backward. Across all 8 steps, left moved a total of 7 positions, not 7 positions per step — that's the amortized O(n) at work.

The general variable-window template

function template(arr, condition) {
  let left = 0;
  let state = /* running total, count, or map */ 0;

  for (let right = 0; right < arr.length; right++) {
    // 1. expand: fold arr[right] into state

    while (/* state violates the condition */ false) {
      // 2. shrink: undo arr[left] from state, then left++
      left++;
    }

    // 3. update the answer using the current valid window [left, right]
  }
}

See the window move

Watch left jump rather than crawl. That jump is what keeps the whole scan linear even though the window shrinks and grows.

Recognizing it in an unseen problem

• The words "contiguous subarray" or "substring" (not subsequence)
• "Longest," "shortest," "maximum," or "minimum" over a contiguous range
• A brute force would check every [i, j] pair — O(n²) or worse
• The condition can be checked/updated incrementally as the window changes