contentintech
Learn/DSA/Sliding Window
AlgorithmsIntermediate10 min

Sliding Window

Maintain a moving range over an array or string, reusing work between steps to hit O(n) instead of O(n·k).

Sliding WindowArraysStrings

A sliding window is a contiguous range — a subarray or substring — that you slide across the input while maintaining a running summary of what is inside it. The insight: when the window moves one step, you do not recompute from scratch. You add the element entering on the right and remove the one leaving on the left. That reuse is what collapses a naive O(n·k) into O(n).

The trigger: the problem asks about a contiguous subarray or substring — a longest, shortest, or best window satisfying some condition. If you catch yourself writing a nested loop that re-scans a range for every start index, that recomputation is the exact waste a window eliminates.

Array
5
0
8
1
12
2
3
3
9
4
21
5
accessed — O(1)shifting — O(n)
Access is O(1); insert/delete shift elements → O(n).
A window of contiguous elements slides right one step at a time — the running sum updates in O(1) instead of re-scanning.

Fixed window: maximum sum of size k

When the window size is a fixed k, compute the first window's sum once, then slide: each step adds the new right element and subtracts the old left one. The sum stays current in O(1) per step, so the whole scan is O(n) — no matter how big k is.

Max sum of any subarray of size k — O(n)
function maxSumOfSizeK(nums, k) {
  let windowSum = 0
  for (let i = 0; i < k; i++) windowSum += nums[i]  // first window
  let best = windowSum
  for (let r = k; r < nums.length; r++) {
    windowSum += nums[r] - nums[r - k]  // slide: +new -old
    best = Math.max(best, windowSum)
  }
  return best
}

The O(n·k) → O(n) win

The brute force recomputes each window's sum from scratch — n windows × k work each = O(n·k). The sliding window reuses the previous sum and touches each element exactly twice (once entering, once leaving), giving a flat O(n).

Variable window: the grow / shrink invariant

When the size is not fixed, the window breathes. You extend the right edge to grow the window greedily, and whenever it violates the constraint you advance the left edge to shrink it back to validity. The rule to internalise: grow to explore, shrink to stay legal, record the best legal window seen. Each pointer only ever moves right, so the total work is O(n).

Longest substring without repeating characters — O(n)
function lengthOfLongestSubstring(s) {
  const lastSeen = new Map()  // char -> last index
  let left = 0, best = 0
  for (let right = 0; right < s.length; right++) {
    const c = s[right]
    // if c is already in the window, jump left past its last position
    if (lastSeen.has(c) && lastSeen.get(c) >= left) {
      left = lastSeen.get(c) + 1  // shrink to restore uniqueness
    }
    lastSeen.set(c, right)
    best = Math.max(best, right - left + 1)  // record best window
  }
  return best
}

Notice the shrink is not a slow one-at-a-time loop here — because we track each character's last index, we can jump left forward in a single move. The general variable-window template uses a while loop to shrink, but the invariant is identical: keep the window valid, and the answer is the largest (or smallest) valid window you ever held.

The mental checklist

  1. Decide fixed vs. variable: is the window size given (k) or defined by a condition?
  2. Choose the window state — a running sum, a count, or a hash map of contents.
  3. On each step, add the entering element to the state.
  4. While the window is invalid, advance left and remove the leaving element.
  5. After adjusting, record the answer (longest, shortest, or best).

Windows need contiguity

Sliding window only works on contiguous ranges. If the problem allows skipping elements (subsequences, not subarrays), a window will not apply — you likely need dynamic programming or a different pattern.

Why it is always O(n)

Both edges of the window march strictly left-to-right and never back up. Each element is added once when right passes it and removed at most once when left passes it — at most 2n operations total. That amortised accounting is the heart of why the pattern is linear, even though there is a nested while in the variable version.

Next up

Two pointers and sliding windows are iterative. The next lesson steps into recursion & backtracking — solving a problem by breaking it into smaller versions of itself.

Section navigation