Algorithms from zero

The sliding window

Crux A window [left, right] slides across an array. Instead of recomputing a property for every subarray (O(n²)), you slide and update in O(1) per step for O(n) total. Two shapes: fixed-size (length k) and variable-size (grow/shrink based on condition).

◷ 20 min

You have an array and a problem that asks for the maximum sum of any 5 consecutive elements. The naive approach: compute the sum of every possible window of length 5 by recalculating from scratch. That is O(n × 5) = O(n). But what if you already know the sum of one window? You can remove the leftmost element and add the new rightmost element, updating the sum in O(1). Slide the window across the array, updating once per step. Total: O(n) instead of recomputing. This is the sliding window technique.

Goal

After this lesson you can recognize when a sliding window applies, implement fixed-size windows (constant length k) and variable-size windows (grow and shrink under a condition), understand why they reduce O(n²) or worse to O(n), and solve classic problems: maximum sum of k consecutive elements, and the smallest subarray with sum ≥ target.

The idea

Sliding window is a technique where a contiguous range [left, right] moves across an array. Instead of recomputing a property (like sum) for every possible subarray — which costs O(n²) or worse — you maintain that property as you slide the window, updating it in O(1) per step.

Two main shapes:

1. Fixed-size window (constant length k)

The window always has length k. Start by computing the property (e.g., sum) for the first k elements. Then slide:

Remove the element at position left from the property.
Add the element at position left + k to the property.
Advance left by 1.

Repeat until the right edge reaches the end of the array.

let left = 0;
let windowSum = sum of arr[0..k-1];
let maxSum = windowSum;

for (let right = k; right < arr.length; right++) {
  // Remove arr[left], add arr[right]
  windowSum = windowSum - arr[left] + arr[right];
  maxSum = Math.max(maxSum, windowSum);
  left++;
}

2. Variable-size window (grow and shrink under a condition)

The window grows by moving right forward. When a condition becomes false (e.g., sum exceeds target), the window shrinks by moving left forward. Continue until right reaches the end.

let left = 0;
let windowSum = 0;
let result = /* store results */;

for (let right = 0; right < arr.length; right++) {
  // Grow: add arr[right]
  windowSum += arr[right];
  
  // Shrink while condition is violated
  while (windowSum > target && left <= right) {
    windowSum -= arr[left];
    left++;
  }
  
  // Process the valid window
  result.push({ left, right, sum: windowSum });
}

Why it works:

A naive approach checks every possible subarray. For n elements, there are O(n²) subarrays. Computing a property for each one costs O(n²) or O(n³).

Sliding window: the window carries running state (a sum, a count, etc.). Each slide — adding or removing one element — updates the state in O(1). Since the window slides across the array at most twice (left and right each move at most n times), the total is O(n).

Key insight: the state is incremental.

If you know the sum of [left, right], the sum of [left+1, right] is sum - arr[left]. The sum of [left, right+1] is sum + arr[right+1]. These updates are O(1), enabling the whole algorithm to be O(n).

The code

Let us code fixed-size and variable-size sliding windows.

1. Fixed-size: maximum sum of k consecutive elements

Given arr = [1, 4, 2, 10, 2, 3, 1, 0, 20] and k = 3, find the maximum sum.

function maxSumFixedWindow(arr, k) {
  if (arr.length < k) return null;
  
  // Compute sum of the first window
  let windowSum = 0;
  for (let i = 0; i < k; i++) {
    windowSum += arr[i];
  }
  
  let maxSum = windowSum;
  
  // Slide the window
  for (let right = k; right < arr.length; right++) {
    // Remove the leftmost element, add the new rightmost
    windowSum = windowSum - arr[right - k] + arr[right];
    maxSum = Math.max(maxSum, windowSum);
  }
  
  return maxSum;
}

2. Variable-size: smallest subarray with sum ≥ target

Given arr = [2, 3, 1, 2, 4, 3] and target = 7, find the smallest subarray with sum ≥ 7.

function minSubarrayLength(arr, target) {
  let left = 0;
  let windowSum = 0;
  let minLength = Infinity;
  
  for (let right = 0; right < arr.length; right++) {
    // Grow: add the right element
    windowSum += arr[right];
    
    // Shrink while the window sum is too large and valid
    while (windowSum >= target && left <= right) {
      // Record this valid window
      minLength = Math.min(minLength, right - left + 1);
      
      // Shrink: remove the left element
      windowSum -= arr[left];
      left++;
    }
  }
  
  return minLength === Infinity ? 0 : minLength;
}

Try running these:

function maxSumFixedWindow(arr, k) {
if (arr.length < k) return null;

let windowSum = 0;
for (let i = 0; i < k; i++) {
  windowSum += arr[i];
}

let maxSum = windowSum;

for (let right = k; right < arr.length; right++) {
  windowSum = windowSum - arr[right - k] + arr[right];
  maxSum = Math.max(maxSum, windowSum);
}

return maxSum;
}

function minSubarrayLength(arr, target) {
let left = 0;
let windowSum = 0;
let minLength = Infinity;

for (let right = 0; right < arr.length; right++) {
  windowSum += arr[right];
  
  while (windowSum >= target && left <= right) {
    minLength = Math.min(minLength, right - left + 1);
    windowSum -= arr[left];
    left++;
  }
}

return minLength === Infinity ? 0 : minLength;
}

const arr = [1, 4, 2, 10, 2, 3, 1, 0, 20];
console.log("Max sum of 3 consecutive:", maxSumFixedWindow(arr, 3));

const arr2 = [2, 3, 1, 2, 4, 3];
console.log("Min subarray length (sum >= 7):", minSubarrayLength(arr2, 7));
console.log("Min subarray length (sum >= 15):", minSubarrayLength(arr2, 15));

Output

Step-by-step trace

Let us trace the fixed-size window on [1, 4, 2, 10, 2, 3, 1, 0, 20] with k = 3:


      1
      function maxSumFixedWindow(arr, k) {
    

      2
        let windowSum = arr[0] + arr[1] + arr[2];
    

      3
        let maxSum = windowSum;
    

      4
        for (let right = k; right < arr.length; right++) {
    

      5
          windowSum = windowSum - arr[right - k] + arr[right];
    

      6
          maxSum = Math.max(maxSum, windowSum);
    

      7
        }
    

      8
        return maxSum;
    

      9
      }

Now trace the variable-size window on [2, 3, 1, 2, 4, 3] looking for sum ≥ 7:


      1
      function minSubarrayLength(arr, target) {
    

      2
        let left = 0, windowSum = 0, minLength = Infinity;
    

      3
        for (let right = 0; right < arr.length; right++) {
    

      4
          windowSum += arr[right];
    

      5
          while (windowSum >= target && left <= right) {
    

      6
            minLength = Math.min(minLength, right - left + 1);
    

      7
            windowSum -= arr[left];
    

      8
            left++;
    

      9
          }
    

      10
        }
    

      11
        return minLength;
    

      12
      }

Complexity

Both fixed-size and variable-size windows process each array element at most twice (once when expanding, once when contracting or sliding):

Problem	Time	Space	Notes
Maximum sum of k consecutive (fixed)	O(n)	O(1)	Single pass, update in O(1) per step
Minimum subarray length (variable)	O(n)	O(1)	left and right each move at most n times total
Longest substring without repeat	O(n)	O(26) or O(k)	Character set size bounds space

Why O(n) and not O(n²)?

Naive approach: for each starting position left, compute the sum/property for all ending positions right. That is O(n²).

Sliding window: the pointers left and right move at most n times each (never backwards, always forward or held steady). The property updates in O(1) per move. Total: O(n) + O(n) = O(n).

Why the window never “un-slides”:

In the variable-size window, left never moves backwards. Once an element leaves the window, the window sum decreases; we never need to add it back. This monotonicity ensures that left and right together move at most 2n times.

Practice 0 / 5

In a fixed-size sliding window of length k, how much time does it take to update the window sum when you slide from position i to i+1?

On array [1, 2, 3, 4, 5], what is the maximum sum of any 2 consecutive elements?

In a variable-size window, why does the left pointer never move backwards (only forward or stay still)?

On array [2, 3, 1, 2, 4, 3], what is the smallest window length with sum ≥ 7?

Which statement best explains why sliding window reduces O(n²) to O(n)?

Common mistake

Forgetting to shrink the variable-size window. If you grow the right pointer but never move the left pointer, you will keep adding elements forever and never record valid windows. For “smallest subarray with sum ≥ target,” you must shrink (move left) as soon as the sum meets the condition, to record the minimal window.

Edge cases

Empty result. For fixed-size windows, if the array has fewer than k elements, there is no window — return null or an empty result. For variable-size windows, if no window meets the condition (e.g., no subarray with sum ≥ target), return 0 or -1 to signal “not found.” Always check these edge cases before returning.

Check yourself

Quiz

Why is the sliding window technique so effective for problems like 'maximum sum of k consecutive elements'?

Recap

The sliding window technique moves a contiguous range [left, right] across an array, updating a property (like sum) incrementally as you go.

Key facts:

Fixed-size window: The window always has length k. Slide by removing the leftmost element and adding the next element to the right. Update in O(1) per step.
Variable-size window: Grow the right edge until a condition is violated. Shrink the left edge until the condition is satisfied. Continue until right reaches the end.
Why O(n)? The window property is updated in O(1) per step (add and remove one element). The pointers move at most n times each (never backward). Total: O(n).
Left pointer never backtracks (variable window). Once the window is valid and we start shrinking, growing again by moving right will only make it larger, never smaller. left moves only forward.
Incremental state is key. If you know the sum of [left, right], the sum of [left+1, right] is sum - arr[left]. No recomputation needed.

Next, you will explore hashing (where the window slides over a set of distinct elements) and more advanced window techniques (longest substring without repeat, and other string problems).

Continue the climb ↑Prefix sums