What is the "sliding window" technique?

AlgorithmsJunior~3 min read

Short answer

The "sliding window" technique is a two-pointer (left/right) approach where we maintain a subarray or substring and efficiently update the answer as the window's boundaries move, avoiding recomputation from scratch. It suits problems about substrings/subarrays, sums/averages, limits on the number of unique elements, and finding maximums/minimums over ranges.

In detail

The idea: instead of recomputing the value for every sub-range from scratch, we gradually extend the window to the right, and once the condition is violated we move the left boundary, maintaining auxiliary structures (a sum, frequency counters, a deque for maximums). This gives linear or near-linear complexity for a wide class of problems.

When to use it

Substrings/subarrays where the answer depends on a contiguous range.
Sums/averages over a fixed-size window k.
Limits on the number of unique elements or the frequency of characters/numbers.
Maximum/minimum over every fixed-length range (monotonic queue/deque).
"Two pointer" problems on strings/arrays with a window invariant.

Window variants

Fixed size k: maintain a metric (a sum/counter), adding on the right and removing on the left.
Variable size: extend the right boundary while the condition holds; if it is violated, shrink from the left.
Monotonic window: maintain a deque of indices so its values are decreasing/increasing, giving O(1) access to the maximum/minimum.

General template

Initialize left = 0, iterate right from 0 to n-1.
Add nums[right]/s[right] to the window, update the counters/structures.
While the invariant is violated, move left, removing elements and updating the structures.
When the invariant holds, update the answer (maximum/minimum/length/sum).

Implementation examples

1) Fixed window: maximum sum of a subarray of length k

Problem: return the maximum sum of any subarray of length k.

function maxSumSubarray(nums, k) {
  if (k > nums.length) return null;
  let windowSum = 0;
  for (let i = 0; i < k; i++) windowSum += nums[i];
  let maxSum = windowSum;
  for (let right = k; right < nums.length; right++) {
    windowSum += nums[right] - nums[right - k];
    if (windowSum > maxSum) maxSum = windowSum;
  }
  return maxSum;
}

console.log(maxSumSubarray([2, 1, 5, 1, 3, 2], 3)); // 9 (5+1+3)

Complexity: O(n) time, O(1) memory.

2) Variable window: length of the longest substring without repeats

Keep a window of unique characters, moving left when a duplicate appears.

function lengthOfLongestSubstring(s) {
  const seen = new Set();
  let left = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    while (seen.has(s[right])) {
      seen.delete(s[left]);
      left++;
    }
    seen.add(s[right]);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

console.log(lengthOfLongestSubstring("abcabcbb")); // 3 ("abc")

Complexity: O(n) time, O(alphabet) memory.

3) Minimum window substring containing all characters of T

Maintain the required character frequencies. Expand the window until the condition holds, then shrink it while minimizing the length.

function minWindow(s, t) {
  if (t.length === 0) return "";
  const need = new Map();
  for (const ch of t) need.set(ch, (need.get(ch) || 0) + 1);

  let have = 0, required = need.size;
  const window = new Map();
  let left = 0, ans = [-1, 0, 0]; // [len, l, r]

  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    window.set(c, (window.get(c) || 0) + 1);
    if (need.has(c) && window.get(c) === need.get(c)) have++;

    while (have === required) {
      if (ans[0] === -1 || right - left + 1 < ans[0]) ans = [right - left + 1, left, right];
      const cl = s[left];
      window.set(cl, window.get(cl) - 1);
      if (need.has(cl) && window.get(cl) < need.get(cl)) have--;
      left++;
    }
  }

  return ans[0] === -1 ? "" : s.slice(ans[1], ans[2] + 1);
}

console.log(minWindow("ADOBECODEBANC", "ABC")); // "BANC"

Complexity: O(n) time, O(alphabet) memory.

4) Maximum in every window of length k (monotonic queue/deque)

Keep indices in a deque so values decrease from left to right. The deque's head is the current window's maximum.

function maxSlidingWindow(nums, k) {
  const deque = []; // indices, values decreasing
  const res = [];

  for (let i = 0; i < nums.length; i++) {
    // 1) Remove indices that fell out on the left
    if (deque.length && deque[0] <= i - k) deque.shift();

    // 2) Keep values decreasing
    while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) {
      deque.pop();
    }
    deque.push(i);

    // 3) Record the maximum once the window has size k
    if (i >= k - 1) res.push(nums[deque[0]]);
  }
  return res;
}

console.log(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3)); // [3,3,5,5,6,7]

Complexity: O(n) time, O(k) memory (the deque).

Common mistakes and how to avoid them

Forgetting to "remove" an element when moving left: correctly decrement the sum/frequencies/clear the Set.
Off-by-one errors: check the indices when recording the answer and the window bounds (right - left + 1).
Updating the answer at the wrong moment: only do it once the window invariant holds.
Trying to sort/rescan the whole range: this breaks linearity.
For maximums/minimums, do not store every element of the window: use a monotonic deque.

Complexity and memory

Fixed window: O(n) time, O(1) memory.
Variable window: O(n) time (each index enters/leaves the window at most once), O(alphabet) memory.
Monotonic window (deque): O(n) time, O(k) memory.

Intuition

Think of the window as a "frame" you smoothly move along: add on the right, remove on the left as needed, keeping enough state to update the answer in O(1). This replaces nested loops and turns many problems into linear ones.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.