Sliding Window — Junior Level¶

Table of Contents¶

1. Introduction
2. Prerequisites
3. The Window Metaphor
4. Glossary
5. Two Flavors of Sliding Window
6. Fixed-Size Window Template
7. Variable-Size Window Template
8. Worked Example 1 — Max Sum of k Consecutive
9. Worked Example 2 — Longest Substring Without Repeating Characters
10. Why It Is O(n)
11. Sliding Window vs Two Pointers
12. Window State Structures
13. Big-O Summary
14. Common Mistakes
15. Edge Cases
16. Cheat Sheet
17. Visual Animation
18. Summary

Introduction¶

Focus: "What is a sliding window?" and "How do I write one?"

The sliding window is a problem-solving technique — not a data structure on its own — that turns many O(n*k) or O(n^2) brute-force scans into clean O(n) algorithms. It works on contiguous segments of an array or string: a "window" defined by two indices [left, right] that slides across the input while you maintain some summary state (a sum, a frequency map, a max, a count).

The technique appears in every coding interview, in production rate limiters, in stream-processing engines, and in observability systems. Once you internalize the two templates below, dozens of problems collapse into the same shape.

Prerequisites¶

• Required: Arrays and strings — indexing, iteration, length.
• Required: Basic loops (for, while) in Go, Java, or Python.
• Required: Hash maps / dictionaries — you will need them as "window state" structures (see topic 05-hash-tables).
• Helpful: Two-pointers technique — sliding window is a structured specialization of it (see topic 10-two-pointers).
• Helpful: Big-O notation basics — to appreciate why the technique is fast.

The Window Metaphor¶

Imagine you are walking past a long wall covered in numbers, looking through a small rectangular window of width k. As you take a step to the right:

1. One new number scrolls into view on the right.
2. One old number scrolls out of view on the left.
3. The numbers in the middle stay where they were.

If you keep a running total of what is inside the window, you do not need to re-sum all k numbers. You add the new one, subtract the old one, and you are done — O(1) work per step. Over n steps, total work is O(n).

That is the entire idea. The "variable" flavor below is just a window whose width changes, but the same expand/shrink discipline applies: each element enters the window at most once and leaves at most once.

Glossary¶

Two Flavors of Sliding Window¶

Every sliding-window problem you will meet falls into one of two shapes.

Flavor 1 — Fixed-Size Window (width = k)¶

You are told a window width k. Both pointers move in lockstep: when right advances by 1, left also advances by 1. The width never changes after the first k elements have been loaded.

Typical question shapes: - "Find the maximum sum of any k consecutive elements." - "Find the average of every window of size k." - "Find the first negative number in every window of size k." - "Return the maximum element in every window of size k." (uses a monotonic deque — see topic 14-monotonic-queue).

Flavor 2 — Variable-Size Window (grow / shrink)¶

The window width is whatever makes the invariant true. Typical invariants: - "No character appears twice." - "At most k distinct characters." - "Sum is at most S." - "All characters of target string are present."

Typical question shapes: - "Longest substring with all distinct characters." - "Smallest substring that contains every character of target T." - "Longest subarray with sum at most K (positive numbers)." - "Longest substring with at most k distinct characters."

The two templates below are the entire pattern. Memorize them.

Fixed-Size Window Template¶

function fixedWindow(a, k):
    initialize window state over a[0..k-1]
    record answer for window [0..k-1]

    for r in k..n-1:
        add    a[r]       to window state    # element scrolls in
        remove a[r-k]     from window state   # element scrolls out
        record answer for window [r-k+1..r]

Two things to notice:

1. The first k elements are loaded once. After that, every iteration does the same two operations: add one, remove one.
2. You record the answer at the end of each step, after the state is fully updated for the new window position.

Variable-Size Window Template¶

function variableWindow(a):
    l = 0
    initialize empty window state
    best = (whatever sentinel — 0, infinity, etc.)

    for r in 0..n-1:
        add a[r] to window state

        while invariant is violated:
            remove a[l] from window state
            l += 1

        # now [l..r] is the largest valid window ending at r
        update best using (r - l + 1) or the current state

Notice that l never moves backwards. Over the whole loop, l advances at most n times and r advances exactly n times — total 2n pointer moves, giving the O(n) bound.

Worked Example 1 — Max Sum of k Consecutive¶

Problem. Given an array of integers and an integer k, find the maximum sum of any contiguous subarray of length k.

Brute force. Try every starting index, sum k elements — O(n*k).

Sliding window. Sum the first k elements. For each subsequent index r, add a[r], subtract a[r-k], update best — O(n).

Go¶

package slidingwindow

import "errors"

// MaxSumK returns the maximum sum of any contiguous subarray of length k.
// Time:  O(n).
// Space: O(1).
func MaxSumK(a []int, k int) (int, error) {
    n := len(a)
    if k <= 0 || k > n {
        return 0, errors.New("invalid window size")
    }

    // Step 1: build the sum of the first window [0..k-1].
    windowSum := 0
    for i := 0; i < k; i++ {
        windowSum += a[i]
    }
    best := windowSum

    // Step 2: slide the window forward one position at a time.
    // Add the new right element, subtract the old left element.
    for r := k; r < n; r++ {
        windowSum += a[r] - a[r-k]
        if windowSum > best {
            best = windowSum
        }
    }
    return best, nil
}

Java¶

public class MaxSumK {

    /**
     * Returns the maximum sum of any contiguous subarray of length k.
     * Time:  O(n).
     * Space: O(1).
     */
    public static int maxSumK(int[] a, int k) {
        int n = a.length;
        if (k <= 0 || k > n) {
            throw new IllegalArgumentException("invalid window size");
        }

        // Step 1: sum the first window.
        int windowSum = 0;
        for (int i = 0; i < k; i++) {
            windowSum += a[i];
        }
        int best = windowSum;

        // Step 2: slide — each step is O(1).
        for (int r = k; r < n; r++) {
            windowSum += a[r] - a[r - k];
            if (windowSum > best) {
                best = windowSum;
            }
        }
        return best;
    }

    public static void main(String[] args) {
        int[] a = {2, 1, 5, 1, 3, 2};
        System.out.println(maxSumK(a, 3)); // 9 (5 + 1 + 3)
    }
}

Python¶

def max_sum_k(a: list[int], k: int) -> int:
    """
    Return the maximum sum of any contiguous subarray of length k.
    Time:  O(n).
    Space: O(1).
    """
    n = len(a)
    if k <= 0 or k > n:
        raise ValueError("invalid window size")

    # Step 1: prime the window with the first k elements.
    window_sum = sum(a[:k])
    best = window_sum

    # Step 2: slide — O(1) per step.
    for r in range(k, n):
        window_sum += a[r] - a[r - k]
        if window_sum > best:
            best = window_sum
    return best


if __name__ == "__main__":
    print(max_sum_k([2, 1, 5, 1, 3, 2], 3))  # 9

Trace on [2, 1, 5, 1, 3, 2], k = 3:

Answer: 9.

Worked Example 2 — Longest Substring Without Repeating Characters¶

Problem. Given a string s, find the length of the longest substring with all distinct characters.

Brute force. For every pair (l, r), check if s[l..r] has all distinct characters — O(n^3) or O(n^2) with a set.

Sliding window (variable). Maintain a set or count map of characters in the window. When s[r] is already in the set, shrink from the left until it is gone. At every step record r - l + 1 as a candidate answer.

Go¶

package slidingwindow

// LongestUnique returns the length of the longest substring of s
// in which every character appears at most once.
// Time:  O(n) — each character enters and leaves the window at most once.
// Space: O(min(n, alphabet)).
func LongestUnique(s string) int {
    count := make(map[byte]int) // character -> occurrences in current window
    best := 0
    l := 0

    for r := 0; r < len(s); r++ {
        count[s[r]]++

        // Invariant: every character in [l..r] appears exactly once.
        // If s[r] now appears twice, shrink from the left until the
        // duplicate is removed.
        for count[s[r]] > 1 {
            count[s[l]]--
            l++
        }

        if r-l+1 > best {
            best = r - l + 1
        }
    }
    return best
}

Java¶

import java.util.HashMap;
import java.util.Map;

public class LongestUnique {

    /**
     * Returns the length of the longest substring with all distinct characters.
     * Time:  O(n). Space: O(min(n, alphabet)).
     */
    public static int longestUnique(String s) {
        Map<Character, Integer> count = new HashMap<>();
        int best = 0;
        int l = 0;

        for (int r = 0; r < s.length(); r++) {
            char c = s.charAt(r);
            count.merge(c, 1, Integer::sum);

            // Shrink from the left until c appears only once in [l..r].
            while (count.get(c) > 1) {
                char left = s.charAt(l);
                count.merge(left, -1, Integer::sum);
                if (count.get(left) == 0) count.remove(left);
                l++;
            }

            best = Math.max(best, r - l + 1);
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(longestUnique("abcabcbb")); // 3 ("abc")
        System.out.println(longestUnique("bbbbb"));    // 1 ("b")
        System.out.println(longestUnique("pwwkew"));   // 3 ("wke")
    }
}

Python¶

def longest_unique(s: str) -> int:
    """
    Length of the longest substring of s with all distinct characters.
    Time:  O(n). Space: O(min(n, alphabet)).
    """
    count: dict[str, int] = {}
    best = 0
    l = 0

    for r, ch in enumerate(s):
        count[ch] = count.get(ch, 0) + 1

        # Invariant: every character in s[l..r] appears at most once.
        while count[ch] > 1:
            left = s[l]
            count[left] -= 1
            if count[left] == 0:
                del count[left]
            l += 1

        if r - l + 1 > best:
            best = r - l + 1
    return best


if __name__ == "__main__":
    print(longest_unique("abcabcbb"))  # 3
    print(longest_unique("bbbbb"))     # 1
    print(longest_unique("pwwkew"))    # 3

Trace on "pwwkew":

Answer: 3.

Why It Is O(n)¶

The killer property of sliding window is the amortized argument:

• right advances exactly n times — once per iteration of the outer loop.
• left advances at most n times in total — it can never go backwards, and it can never pass right.
• Each "add" and each "remove" on the window state takes O(1) (hash map insert/delete, integer add/subtract, set membership).

Total work: at most 2n pointer moves, each doing O(1) state maintenance, giving O(n) total. Even though the inner while loop in the variable-size template looks like it could blow up, it cannot — left has only n total moves to spend across the entire run of the algorithm.

This is the same kind of argument used to prove dynamic arrays amortize to O(1) per push (see topic 01-array).

Sliding Window vs Two Pointers¶

These two patterns are close cousins. Both use a left and a right index walking over an array. The differences:

Rule of thumb: if the problem asks about a contiguous subarray/substring and you need to track something about the entire range, reach for sliding window. If it asks about pairs/triples or two specific positions, reach for two pointers. Topic 10-two-pointers covers the converging pattern; this topic covers the expanding/contracting one.

Window State Structures¶

The "window state" is whatever lets you answer the question in O(1) per step. Pick one to match the problem:

Hash maps are by far the most common — see 05-hash-tables for how they hit O(1) average. For range-sum problems where the window size is fixed, an integer is enough; for range-sum problems on arbitrary ranges that change, prefer prefix sums (see 12-prefix-sums-difference-arrays).

Big-O Summary¶

Common Mistakes¶

Edge Cases¶

• Empty input. Return 0 (or whatever the problem says — be explicit).
• k = 0 (fixed). Usually invalid; reject or return 0.
• k > n (fixed). Usually invalid; reject or return what makes sense (sum of all? max possible?).
• All identical elements. Variable-window "no repeats" must return 1, not n.
• All distinct elements. Variable-window "no repeats" must return n.
• One element. Both templates must handle n = 1 without skipping the init.
• Negative numbers in sum problems. Be very careful — many invariants assume monotonicity.

Cheat Sheet¶

Visual Animation¶

See animation.html for an interactive sliding-window visualizer.

Choose between two demos: - Fixed-size max-sum — pick k, step through, watch the window scroll right. - Longest substring without repeats — watch left shrink whenever a duplicate enters.

The animation highlights the window in blue, shows the live window state (sum or frequency map), and logs every expand/shrink step.

Summary¶

The sliding window technique converts many O(n*k) and O(n^2) brute forces over contiguous array/string ranges into O(n) one-pass algorithms by maintaining a small piece of "window state" and updating it incrementally as the window moves. Two templates cover almost every problem: fixed-size (both pointers move together) and variable-size (right expands, left shrinks while an invariant is violated). The amortized argument — each element enters and leaves at most once — is what gives you the linear bound. Master the two templates, pick the right state structure (sum, set, frequency map, monotonic deque), and you will solve dozens of interview problems with the same code skeleton.