Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Introduction to Sliding Window

Editorial

What is a sliding window?

Your fitness tracker logs your steps every minute. After a year that's 525,600 numbers, and you want your best day: the 1,440 minutes in a row with the most steps.

The obvious way is to add up every stretch of 1,440 minutes and keep the biggest. There are 524,161 stretches, so that's 754,791,840 additions, about 755 million.

Now look at two neighbouring stretches. The one that starts at minute 1 and the one that starts at minute 2 share 1,439 minutes. Only one minute left, and one arrived. So don't add the stretch up again: take the last total, add the minute that arrived and subtract the minute that left. That's two operations per step, 1,049,760 in all: roughly 720 times fewer operations for the same answer.

That's a sliding window: a run of consecutive items that moves along an array one step at a time. It carries a summary of what's inside (here, a sum), and it updates that summary from the item entering and the item leaving instead of recomputing it. This lesson covers windows of a fixed size. The next one, Variable-Size Sliding Window: Longest and Shortest, lets the window grow and shrink.

Sliding window over the array 3, 1, 4, 1, 5, 9, 2, 6 with a window of four numbers. The window 1, 4, 1, 5 sums to 11. When it slides one step right to 4, 1, 5, 9, three numbers stay inside, the 1 on the left leaves and the 9 on the right enters, so the new sum is 11 − 1 + 9 = 19 without adding the window up again. Each slide costs one addition and one subtraction, which makes the whole scan O(n) instead of O(n · k).

Adding up every window: the work it repeats

Take a smaller version. Maximum Average Subarray I gives you nums = [1, 12, -5, -6, 50, 3] and k = 4, and asks for the largest average of 4 numbers in a row. Here's the first thing most people write: try every start, add up the window, keep the best sum.

def max_window_sum_brute(nums, k):
    best = None
    for start in range(len(nums) - k + 1):
        total = 0
        for i in range(start, start + k):    # add up the whole window again
            total += nums[i]
        if best is None or total > best:
            best = total
    return best

It returns 51, the sum of [12, -5, -6, 50], and the answer is 51 / 4 = 12.75. It's correct, but look at what it adds:

WindowNumbersSum
starts at 01, 12, -5, -62
starts at 112, -5, -6, 5051
starts at 2-5, -6, 50, 342

Each window re-adds 3 numbers that the window before it already added. With n numbers there are n − k + 1 windows of k numbers each, so the brute force does (n − k + 1) · k additions. Run on n = 1,000 and k = 100, an instrumented copy counts 90,100 additions; the sliding version below counts 1,900 operations. With k near n / 2 that's O(n²).

Slide: one number in, one number out

Moving the window one step right changes exactly two things: one number joins on the right and one drops off the left. Everything between them stays. So:

new sum = old sum + the number entering − the number leaving

When the window ends at index right, the number entering is nums[right], and the number leaving is nums[right - k]: the one k places back, just outside the new window.

Why is the running sum always right? After each step, window_sum equals the sum of the k numbers ending at right. That's true for the first window, because you added it up. Each step keeps it true, because the new window is the old one without its first number and with the next one. That sentence, the loop's invariant, is the whole proof.

The cost: every number enters once and leaves at most once. That's k operations for the first window and two per slide, k + 2(n − k) in all: O(n) time, and O(1) extra space.

(A prefix-sum array also gives any window's sum in O(1), after O(n) setup. It costs O(n) extra memory, though, and letter counts would need 26 of them. The window keeps only what's inside it.)

Sliding a window of four over Maximum Average Subarray I — The window is shaded. Each step, the glowing number enters and the amber one leaves; the sum changes by exactly those two.

Fixed-size window template

Here's the template for the largest window sum. Change what you track and what you keep, and it solves the rest of this lesson.

long long maxWindowSum(const vector<int>& nums, int k) {
    long long windowSum = 0;
    for (int i = 0; i < k; i++) {
        windowSum += nums[i];               // the first window
    }
    long long best = windowSum;
    for (int right = k; right < (int)nums.size(); right++) {
        windowSum += nums[right];           // the number entering
        windowSum -= nums[right - k];       // the number leaving
        best = max(best, windowSum);
    }
    return best;
}

def max_window_sum(nums, k):
    window_sum = sum(nums[:k])              # the first window
    best = window_sum
    for right in range(k, len(nums)):
        window_sum += nums[right]           # the number entering
        window_sum -= nums[right - k]       # the number leaving
        best = max(best, window_sum)
    return best

static long maxWindowSum(int[] nums, int k) {
    long windowSum = 0;
    for (int i = 0; i < k; i++) {
        windowSum += nums[i];               // the first window
    }
    long best = windowSum;
    for (int right = k; right < nums.length; right++) {
        windowSum += nums[right];           // the number entering
        windowSum -= nums[right - k];       // the number leaving
        best = Math.max(best, windowSum);
    }
    return best;
}

function maxWindowSum(nums, k) {
    let windowSum = 0;
    for (let i = 0; i < k; i++) {
        windowSum += nums[i];               // the first window
    }
    let best = windowSum;
    for (let right = k; right < nums.length; right++) {
        windowSum += nums[right];           // the number entering
        windowSum -= nums[right - k];       // the number leaving
        best = Math.max(best, windowSum);
    }
    return best;
}

Each version prints 51, 5, -3 and 9 for [1, 12, -5, -6, 50, 3] with k = 4, [5] with k = 1, [-3, -1, -2] with k = 2 and [2, 1, 5, 1, 3, 2] with k = 3. Notice the third: every number is negative, and the answer is still a real window, because best starts at the first window's sum, not at 0.

For Maximum Average Subarray I, dividing every sum by the same k never changes which one is biggest. So slide with whole numbers and divide once at the end: 51 / 4 = 12.75. In Java and C++ make that a floating-point division, (double) best / k. The sums fit in a 32-bit int there (at most 10^5 numbers of size 10^4 is 10^9), but the template uses 64-bit sums so you never have to check.

Windows that count letters

Permutation in String asks whether s2 contains some rearrangement of s1. Rearrangements of the same letters have the same letter counts, so the question becomes: is there a window of length len(s1) in s2 whose 26 letter counts equal those of s1? The size is fixed, so slide it: the entering letter's count goes up by one, the leaving letter's goes down by one.

Comparing all 26 counts after every step works, and it's O(26) per step. But there's a neater move. Keep matches: how many of the 26 letters have the same count in the window as in the short string (s1 here, p in the code below). A step changes two counts, and each change is settled by two comparisons: if the letter agreed before the change, it doesn't now (matches − 1); if it agrees after, it does now (matches + 1). When matches is 26, every count agrees and the window is an anagram.

It can't fire too early, either. Before the window holds k letters, its counts add up to fewer than k, so some letter is still short.

Find All Anagrams in a String wants every start. Here it is on s = "cbaebabacd", p = "abc":

Find All Anagrams with a matches counter — The window is shaded. The glowing letter enters and the amber one leaves; matches counts the letters whose counts agree with p. Green means all 26 agree.

vector<int> findAnagrams(const string& s, const string& p) {
    int k = p.size();
    if (k > (int)s.size()) return {};
    vector<int> need(26, 0), have(26, 0);    // letter counts of p and of the window
    for (char ch : p) need[ch - 'a']++;
    int matches = 0;                          // letters whose counts agree
    for (int c = 0; c < 26; c++) {
        if (have[c] == need[c]) matches++;
    }
    vector<int> starts;
    for (int right = 0; right < (int)s.size(); right++) {
        int c = s[right] - 'a';               // the letter entering
        if (have[c] == need[c]) matches--;
        have[c]++;
        if (have[c] == need[c]) matches++;
        if (right >= k) {
            c = s[right - k] - 'a';           // the letter leaving
            if (have[c] == need[c]) matches--;
            have[c]--;
            if (have[c] == need[c]) matches++;
        }
        if (matches == 26) starts.push_back(right - k + 1);   // every letter agrees
    }
    return starts;
}

def find_anagrams(s, p):
    k = len(p)
    if k > len(s):
        return []
    need = [0] * 26                           # letter counts of p
    have = [0] * 26                           # letter counts of the window
    for ch in p:
        need[ord(ch) - ord("a")] += 1
    matches = sum(1 for c in range(26) if have[c] == need[c])   # letters whose counts agree
    starts = []
    for right in range(len(s)):
        c = ord(s[right]) - ord("a")          # the letter entering
        if have[c] == need[c]:
            matches -= 1
        have[c] += 1
        if have[c] == need[c]:
            matches += 1
        if right >= k:
            c = ord(s[right - k]) - ord("a")  # the letter leaving
            if have[c] == need[c]:
                matches -= 1
            have[c] -= 1
            if have[c] == need[c]:
                matches += 1
        if matches == 26:                     # every letter agrees
            starts.append(right - k + 1)
    return starts

static List<Integer> findAnagrams(String s, String p) {
    int k = p.length();
    List<Integer> starts = new ArrayList<>();
    if (k > s.length()) return starts;
    int[] need = new int[26], have = new int[26];   // letter counts of p and of the window
    for (char ch : p.toCharArray()) need[ch - 'a']++;
    int matches = 0;                                 // letters whose counts agree
    for (int c = 0; c < 26; c++) {
        if (have[c] == need[c]) matches++;
    }
    for (int right = 0; right < s.length(); right++) {
        int c = s.charAt(right) - 'a';               // the letter entering
        if (have[c] == need[c]) matches--;
        have[c]++;
        if (have[c] == need[c]) matches++;
        if (right >= k) {
            c = s.charAt(right - k) - 'a';           // the letter leaving
            if (have[c] == need[c]) matches--;
            have[c]--;
            if (have[c] == need[c]) matches++;
        }
        if (matches == 26) starts.add(right - k + 1);   // every letter agrees
    }
    return starts;
}

function findAnagrams(s, p) {
    const k = p.length;
    if (k > s.length) return [];
    const need = new Array(26).fill(0);       // letter counts of p
    const have = new Array(26).fill(0);       // letter counts of the window
    const code = ch => ch.charCodeAt(0) - 97;
    for (const ch of p) need[code(ch)]++;
    let matches = 0;                          // letters whose counts agree
    for (let c = 0; c < 26; c++) {
        if (have[c] === need[c]) matches++;
    }
    const starts = [];
    for (let right = 0; right < s.length; right++) {
        let c = code(s[right]);               // the letter entering
        if (have[c] === need[c]) matches--;
        have[c]++;
        if (have[c] === need[c]) matches++;
        if (right >= k) {
            c = code(s[right - k]);           // the letter leaving
            if (have[c] === need[c]) matches--;
            have[c]--;
            if (have[c] === need[c]) matches++;
        }
        if (matches === 26) starts.push(right - k + 1);   // every letter agrees
    }
    return starts;
}

Each prints [0, 6], [0, 1, 2] and [] for ("cbaebabacd", "abc"), ("abab", "ab") and ("a", "ab"): the last has no window at all, because p is longer than s.

Permutation in String is the same loop that returns true at the first window where matches reaches 26.

Maximum Points You Can Obtain from Cards: slide over what you leave

Cards lie in a row, [1, 2, 3, 4, 5, 6, 1], and you take k = 3 of them, each from the front or the back. The taken cards can split between the two ends in k + 1 ways, which looks nothing like a window.

Turn it around. Whatever you take, the cards you leave are one unbroken block of n − k = 4 in the middle. Your score is the total, 22, minus that block. So the best score comes from the smallest block of n − k cards: a fixed window again.

Maximum Points You Can Obtain from Cards with cards 1, 2, 3, 4, 5, 6, 1 and k = 3. The four ways to take three cards from the two ends each leave one block of four cards in the middle: leaving 4, 5, 6, 1 (sum 16) scores 6; leaving 3, 4, 5, 6 (sum 18) scores 4; leaving 2, 3, 4, 5 (sum 14) scores 8; leaving 1, 2, 3, 4 (sum 10) scores 12. The score is the total, 22, minus the block left behind, so the best score, 12, comes from leaving the smallest block, 1, 2, 3, 4. A window of n − k cards slides over the row to find it.
def max_score(card_points, k):
    n = len(card_points)
    size = n - k                              # the cards you leave: one block of n - k
    window_sum = sum(card_points[:size])
    smallest = window_sum
    for right in range(size, n):
        window_sum += card_points[right]          # the card entering
        window_sum -= card_points[right - size]   # the card leaving
        smallest = min(smallest, window_sum)
    return sum(card_points) - smallest

It prints 12, 4 and 55 for the problem's three examples. When k = n you take every card, the block is empty, and the score is the total. The window could also be k cards that wrap from the back to the front; either way it's one fixed window and one pass.

When to use a fixed window

Clues in the problem statement:

  • "every k consecutive", "subarray of length k", "substring of size k": the size is given.
  • "an anagram / a permutation of p inside s": the size is len(p), and the summary is letter counts.
  • "take k items from the two ends": slide over the block you leave.
  • A summary you can undo: a sum, counts, how many items have some property.

Near-misses that look similar:

  • "subsequence": the items needn't be next to each other, so there's no window. That's Two Pointers (Is Subsequence) or dynamic programming.
  • "the longest / shortest subarray such that…": the size isn't given. That's the next lesson.
  • "the maximum of every window": a fixed window, but the maximum can't be undone (below).
  • "subarrays that sum to k" with negative numbers: prefix sums with a hash map, in the Prefix Sum section.

When a fixed window doesn't work

The slide rests on one thing: when a number leaves, you can undo its effect. A sum can (subtract). Counts can (decrement). The maximum can't.

Take windows of 3 over [9, 4, 7, 2, 6]. The first window's maximum is 9. Slide: 9 leaves and 2 enters. What's the new maximum? Nothing you kept says. The answer, 7, was inside the window all along, and only a rescan finds it, which costs O(k) per step and brings back O(n · k). Sliding Window Maximum keeps a deque of the numbers that could still become the maximum, and gets O(n). The median has the same problem; Sliding Window Median uses two heaps.

And when the window's size isn't fixed, there's no single k to slide: that's the next lesson.

Common mistakes

Subtracting the wrong number. window_sum -= nums[right - k + 1]

On [1, 12, -5, -6, 50, 3] with k = 4 it returns 48, not 51. The number leaving is the one just outside the new window, k places back: nums[right - k]. nums[right - k + 1] is still inside.

Starting best at 0. best = 0

On [-3, -1, -2] with k = 2 it returns 0, a sum no window has; the answer is -3. Start best at the first window's sum, or at minus infinity.

Counting windows that aren't full yet. best = max(best, window_sum) on every step

On [5, -10, 1] with k = 2 it returns 5: the lone 5 before the window filled up. The real windows sum to -5 and -9. Only compare once right >= k - 1.

Dividing two ints for the average. return best / k; in Java

On [1, 12, -5, -6, 50, 3] with k = 4 it prints 12.0, not 12.75: 51 / 4 is integer division. Write (double) best / k. (C++ does the same; Python's / doesn't.)

Forgetting to remove the leaving letter.

Drop the if right >= k: block from find_anagrams and ("abab", "ab") returns [0] instead of [0, 1, 2]. The counts keep growing, so after the first window they never match again.

Check yourself

Quiz

1 / 5

Multiple choice

The window nums[2..5] sums to 40. To slide it to nums[3..6], what do you do?

Practice problems

From easier to harder:

  1. Maximum Average Subarray I: the template, then divide once.
  2. Maximum Points You Can Obtain from Cards: slide over the cards you leave.
  3. Permutation in String: letter counts, stop at the first match.
  4. Find All Anagrams in a String: letter counts, every match.

Next: Variable-Size Sliding Window: Longest and Shortest, where the window grows on the right and shrinks on the left.