Sliding Window Technique — Complete Guide (DSA)

Source: Dev.to

What is the Sliding Window Technique?

The sliding window is an algorithmic technique used to efficiently process a contiguous subarray or substring of fixed or variable size within an array or string.
Instead of recomputing values for every subarray from scratch, the window reuses the previous computation while moving forward.

• Window size (k) – the number of elements examined at once.
• Window – the group of elements currently being processed.

Fixed‑size window example

Array: [1, 3, -1, -3, 5, 3, 6, 7] k = 3

[1, 3, -1]
   [3, -1, -3]
      [-1, -3, 5]
         [-3, 5, 3]
            [5, 3, 6]
               [3, 6, 7]

For each window we can compute a property (e.g., maximum) without scanning the whole window again.

Result (maximum of each window): [3, 3, 5, 5, 6, 7]

How the Sliding Window Works

1. Process the first window (indices 0 … k‑1).
2. For each subsequent index i = k … n‑1
   • Remove the element that leaves the window (i‑k).
   • Add the new element (i).
   • Update the answer using only the changed elements.

This reduces the naive O(n·k) work to O(n).

Example: Maximum Sum Subarray of Size k

// Time: O(n)   Space: O(1)
function maxSumSubarray(arr, k) {
  let windowSum = 0;
  let maxSum = -Infinity;

  // first window
  for (let i = 0; i = k - 1) {
      result.push(nums[deque[0]]);
    }
  }

  return result;
}

Variable‑size Window (Two‑Pointer) Technique

When the window size is not known in advance, we expand the right pointer until a condition becomes invalid, then shrink from the left.

// Example: Length of the longest substring without repeating characters
function longestUnique(s) {
  const set = new Set();
  let left = 0;
  let maxLen = 0;

  for (let right = 0; right < s.length; right++) {
    while (set.has(s[right])) {
      set.delete(s[left]);
      left++;
    }
    set.add(s[right]);
    maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;
}

General pattern

left = 0
for right in range(0, n):
    expand window (include element at right)

    while window does not satisfy condition:
        shrink window (exclude element at left)
        left += 1

    update answer based on current window

Common Applications

Typical real‑world scenarios:

• Peak bandwidth usage in the last 5 minutes.
• Maximum price in the last 30 days.
• Average temperature of the last 10 readings.
• Detecting anomalies in the last N requests.

Why the Sliding Window Gives O(n)

The technique is essentially a specialized two‑pointer method:

• The right pointer always moves forward, expanding the window.
• The left pointer moves forward only when the current window violates a condition.

Because each element is added to and removed from the window at most once, the total work is linear in the input size.

Common Pitfalls

• Forgetting to remove the leftmost element when the window slides.
• Using a naïve nested loop that recomputes the whole window each time (leads to O(n·k)).
• Assuming a fixed‑size solution (deque) works for variable‑size problems; they require the two‑pointer shrink‑expand approach.

Summary

The sliding window technique transforms many subarray/subsequence problems from quadratic to linear time by reusing previous computations and maintaining only the necessary state as the window moves across the data. Whether the window size is fixed (using a deque) or variable (using two pointers), the core idea remains the same: process each element at most twice—once when it enters the window and once when it leaves.