Sliding Window: The Technique for Contiguous Subarrays & Substrings

The sliding window is a technique for problems that ask about a contiguous run of elements — a subarray or substring — where you maintain a “window” over the data and slide it forward instead of re-examining every range from scratch. It turns many naive O(n²) scans into a single O(n) pass by reusing the work already done as the window moves.

The core idea

Imagine a window — a left edge l and a right edge r — framing a stretch of the array. Brute force would, for every possible start, re-scan to every possible end: that’s O(n²) ranges. The sliding window keeps a running summary of what’s inside the window (a sum, a count, a character frequency map) and updates it incrementally:

• Add the element entering on the right.
• Remove the element leaving on the left.

Because each element enters and leaves the window at most once, the total work is O(n).

// Sum of every contiguous window of size 3 — the window "slides"
#include <vector>
std::vector<int> windowSums(const std::vector<int>& a, int k) {
    std::vector<int> out;
    int sum = 0;
    for (int r = 0; r < (int)a.size(); r++) {
        sum += a[r];                 // element enters on the right
        if (r >= k) sum -= a[r - k]; // element leaves on the left
        if (r >= k - 1) out.push_back(sum);
    }
    return out;
}

// Sum of every contiguous window of size 3 — the window "slides"
int[] windowSums(int[] a, int k) {
    int[] out = new int[a.length - k + 1];
    int sum = 0;
    for (int r = 0; r < a.length; r++) {
        sum += a[r];                 // element enters on the right
        if (r >= k) sum -= a[r - k]; // element leaves on the left
        if (r >= k - 1) out[r - k + 1] = sum;
    }
    return out;
}

// Sum of every contiguous window of size 3 — the window "slides"
function windowSums(a, k) {
  const out = [];
  let sum = 0;
  for (let r = 0; r < a.length; r++) {
    sum += a[r];                  // element enters on the right
    if (r >= k) sum -= a[r - k];  // element leaves on the left
    if (r >= k - 1) out.push(sum);
  }
  return out;
}

# Sum of every contiguous window of size 3 — the window "slides"
def window_sums(a, k):
    out = []
    s = 0
    for r in range(len(a)):
        s += a[r]                 # element enters on the right
        if r >= k:
            s -= a[r - k]         # element leaves on the left
        if r >= k - 1:
            out.append(s)
    return out

When the technique applies

Reach for a sliding window when the problem has all three of these signs:

• It asks about a contiguous subarray or substring (order matters; you cannot skip elements).
• You want an optimum or count over those ranges — longest, shortest, maximum sum, number of valid windows.
• The window’s summary can be updated incrementally as elements join and leave.

For beginners: “Contiguous” is the keyword. Subsequence problems (where you may skip elements) are usually not sliding window — those often need dynamic programming. A subarray or substring is always contiguous.

The two flavors

There are two shapes you’ll meet again and again:

1. Fixed-size window — the window is always exactly k wide. You slide it one step at a time. See fixed-size window.
2. Variable-size window — the window grows and shrinks to satisfy a condition (longest substring without repeats, smallest window covering a target). See variable-size window.

A closely related idea is prefix sums, which precompute cumulative totals so any range sum is O(1) — handy when the window isn’t moving in a simple sweep. See prefix sums.

Why it beats brute force

Going deeper: The sliding window is really the two-pointers technique specialized to a contiguous region: both pointers move forward only, never backward, which is exactly why the amortized cost stays linear.

Ready to apply it? Start with the fixed-size window, then practice on the exercises.