Lesson 5 · Core algorithms

Sliding Window Technique

Sliding Window is a subset of two pointers used to track a contiguous subset of elements. Instead of recalculating a property (like a sum) for every possible window, it updates the property by removing the element leaving the window and adding the element entering it.

Reusing the Overlap

The sliding window applies to problems asking about contiguous subarrays or substrings. Examining every one of them is O(n²), and the technique removes that factor by noticing that consecutive windows share almost all their elements.

Consider the maximum sum of any 5 consecutive elements. The naive approach sums each group of 5 separately, so an array of n elements does 5n additions and repeats nearly all of them — the window at position i and the window at i+1 differ by exactly two elements.

So do not recompute. Subtract the element leaving on the left, add the element arriving on the right, and the new sum is available in O(1). The whole scan becomes O(n) with a handful of arithmetic operations per step.

That is the entire principle, and it generalises well past sums: maintain a summary of the window's contents and update it incrementally as the boundaries move. The summary can be a sum, a count of distinct values, a frequency map, or a monotonic deque of candidates — anything that can be adjusted rather than rebuilt.

The requirement this imposes is worth stating explicitly, because it is what determines whether the technique applies at all: the state must be updatable both when an element enters and when one leaves. A sum qualifies, since addition has an inverse. A maximum does not — removing the largest element leaves no way to recover the next largest without rescanning, which is exactly why maximum-in-window needs a monotonic deque rather than a plain variable.

Consecutive windows overlap almost entirely — reuse that
Subtract what leaves, add what arrives: O(1) per step
The summary can be a sum, a count, a frequency map, or a deque
It must be updatable on both entry and exit, or the technique fails

Fixed-Size Windows

When the window's width k is given, the structure is the simplest of the two. Build the first window over the first k elements, then slide it one position at a time to the end of the array.

Each slide is two updates and one comparison: remove the element at i − k, add the element at i, then record the result if it beats the best seen. The window's size never changes, so there is no decision about when to grow or shrink — the loop is mechanical.

The one detail that causes bugs is the boundary at initialisation. Either build the first window in a separate loop and then slide from index k, or use a single loop that only starts recording once i >= k − 1. Mixing the two produces answers computed over an incomplete first window, which is wrong in a way that small test cases often miss.

Maximum sum of a subarray of size k is the canonical example. Average of every window of size k is the same loop with a division. Maximum in every window of size k looks similar but is genuinely harder, because a maximum cannot be decremented on removal; it needs a monotonic deque holding indices whose values decrease, so the front is always the current maximum. That variant is O(n) overall because each index is pushed and popped exactly once.

Build the first window, then slide one position at a time
Two updates per step: remove the departing element, add the arriving one
Start recording only once the window is genuinely full
Window maximum needs a monotonic deque, not a single variable

Variable-Size Windows

When the width is not given but a condition is — the longest substring with no repeated character, the shortest subarray summing to at least a target — both boundaries move independently, and the shape changes.

The pattern is two nested-looking loops that are not nested in cost. The outer loop advances right by one each iteration, expanding the window and adding the new element to the state. The inner while loop advances left, shrinking the window and removing elements, and runs only while the window needs correcting.

What the inner loop tests depends on which of two families the problem belongs to, and getting this backwards is the most common error. For a longest problem, shrink while the window is invalid, then record after the loop — the window is always valid at that point. For a shortest problem, shrink while the window is still valid, recording before each shrink — you are pushing to find the smallest window that still qualifies.

The complexity argument deserves stating because the code looks quadratic. left never moves backwards, and it can advance at most n times across the entire run. So the inner loop's total iterations over the whole algorithm are bounded by n, not by n per outer step. Each index enters the window once and leaves once, giving O(n) overall.

The technique's real precondition is a monotonicity property: shrinking the window from the left must be capable of restoring validity. Where that holds — sums of non-negative numbers, counts of distinct characters — the method works. Where it does not, as with subarray sums permitting negative numbers, shrinking can make things worse and the sliding window silently returns wrong answers; that case needs prefix sums with a hash map instead.

The two families, and what changes between them
Goal	Shrink while	Record	Example
Longest valid window	The window is invalid	After shrinking	Longest substring without repeats
Shortest valid window	The window is valid	Before each shrink	Minimum subarray sum ≥ target
Exactly k distinct	Reduce to atMost(k) − atMost(k−1)	—	Subarrays with k distinct values

right always expands; left shrinks only while correction is needed
Longest: shrink while invalid. Shortest: shrink while valid
left never retreats, so total work is O(n) despite the inner loop
Negative numbers break the monotonicity the technique relies on

Key reference

Terms, operations, and practical uses

Core vocabulary

WindowA contiguous sequence of elements in an array or string bounded by two indices (left and right).
Fixed SizeA window where the distance between the left and right pointers remains exactly K.
Dynamic SizeA window that grows or shrinks as needed to satisfy a particular condition.

Operations

ExpandIncreasing the window size by moving the right pointer and including a new element in the state.
ShrinkDecreasing the window size by moving the left pointer and removing its element from the state.
State UpdateModifying the running metric (sum, product, frequency map) in O(1) time when the window boundaries change.

Data structures

Hash Map / DictionaryUsed to keep track of character frequencies or counts of elements currently inside the window.
Frequency ArrayA fixed-size array (like int[128]) often used instead of a Hash Map for ASCII string problems to improve speed.
DequeA double-ended queue used in monotonic sliding window problems (like finding the maximum in every window of size K).

Implementation

Maximum sum of any contiguous subarray of size 3

def max_sum(arr, k):
    window_sum = sum(arr[:k])
    max_val = window_sum
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i-k]
        max_val = max(max_val, window_sum)
    return max_val
print(max_sum([2, 1, 5, 1, 3, 2], 3), '(from [5, 1, 3])')

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int maxSum(vector<int>& arr, int k) {
    int windowSum = 0;
    for (int i = 0; i < k; i++) windowSum += arr[i];
    int maxVal = windowSum;
    for (int i = k; i < arr.size(); i++) {
        windowSum += arr[i] - arr[i - k];
        maxVal = max(maxVal, windowSum);
    }
    return maxVal;
}
int main() {
    vector<int> arr = {2, 1, 5, 1, 3, 2};
    cout << maxSum(arr, 3) << " (from [5, 1, 3])\n";
}

public class Main {
    static int maxSum(int[] arr, int k) {
        int windowSum = 0;
        for (int i = 0; i < k; i++) windowSum += arr[i];
        int maxVal = windowSum;
        for (int i = k; i < arr.length; i++) {
            windowSum += arr[i] - arr[i - k];
            maxVal = Math.max(maxVal, windowSum);
        }
        return maxVal;
    }
    public static void main(String[] args) {
        int[] arr = {2, 1, 5, 1, 3, 2};
        System.out.println(maxSum(arr, 3) + " (from [5, 1, 3])");
    }
}

Watch it run

Step through it

Running on array = [2, 1, 5, 1, 3, 2], k = 3

Output

Read all 8 Steps

Initial window Sum the first 3 elements: 2 + 1 + 5 = 8. Max is 8.
Slide window right Move window one step. Add arr[3] (1) and subtract arr[0] (2).
Update max New sum is 8 + 1 - 2 = 7. Max is still 8.
Slide window right Move window one step. Add arr[4] (3) and subtract arr[1] (1).
Update max New sum is 7 + 3 - 1 = 9. Max updates to 9.
Slide window right Move window one step. Add arr[5] (2) and subtract arr[2] (5).
Update max New sum is 9 + 2 - 5 = 6. Max remains 9.
Done Reached the end of the array. The maximum sum found is 9, produced by [5, 1, 3].

Recognising One, and the State to Keep

The signals are consistent. The problem says contiguous — subarray or substring, not subsequence. It asks for a longest, shortest, or maximum over such ranges. And the obvious solution is a nested loop over all start and end pairs. That combination is a sliding window unless something breaks the monotonicity.

The subsequence distinction is worth checking first, since it is the fastest disqualifier. A subsequence permits skipping elements, so there is no window to slide, and those problems are almost always dynamic programming instead.

Choosing the state is the design decision. A running sum or count suffices for arithmetic conditions. A frequency map — character to count — handles anagrams, distinct-character limits, and 'contains all of these' problems; pair it with a counter of how many distinct keys are currently over or at target so validity is an O(1) test rather than a scan of the map.

That last point is where an otherwise-correct solution loses its complexity. If checking validity means iterating the frequency map, the window is O(n) per step and the whole thing is O(n·k). Maintaining a single integer — how many characters currently satisfy the requirement — keeps the check O(1) and the algorithm O(n).

A useful reframing for the harder counting problems: exactly k is rarely computed directly. Instead compute at most k and subtract at most k−1, since each of those is a straightforward variable window. It is a standard trick and turns a problem that resists the technique into two that do not.

Contiguous range plus a longest/shortest/max ask signals a window
Subsequence problems are not window problems — usually DP
Keep validity checkable in O(1), not by scanning the frequency map
Compute 'exactly k' as atMost(k) − atMost(k−1)