Skip to content

Sliding Window

Lesson 2 of 7 in Core Patterns · 35 min · Beginner

A frame that slides along; you only update its edges.

Introduction

A delivery app logs its orders hour by hour. How do you find the busiest 3-hour stretch of the day without adding up every stretch from scratch?

You have 24 numbers, one per hour: 4, 7, 3, 9, 12, 8, 5, and so on. The slow way adds up every possible stretch separately: 22 stretches, 3 numbers each, 66 additions in total.

Now look at two neighbouring stretches, hours 3 to 5 and hours 4 to 6. They share two of their three hours. Why add those two again?

Lesson overview

This lesson will show you how to:

  • Explain why sliding a window beats re-adding overlapping stretches.
  • Trace a fixed-size window across an array and update its sum.
  • Grow and shrink a variable window until its condition holds again.
  • Spot "contiguous", "subarray" or "substring" wording in a problem.
  • Compare the fixed-size and variable-size window templates.

The picture

nums201152133425leftrightthe windowadd on the rightdrop on the leftArray nums with 6 slots: 2, 1, 5, 1, 3, 2. Pointers: left at index 1; right at index 3. Window from index 1 to 3.

Mental model

Sit by a train window and you only see one slice of the landscape. As the train rolls on, one new tree appears at the front edge and one old tree slips off the back edge.

You never re-look at the trees in the middle. You just notice what entered and what left. A sliding window is that frame laid over an array.

Never recompute the window. When it moves, add the one that entered and subtract the one that left.

Words to know

window
The stretch of neighbouring elements you are looking at right now, from left to right.
expand
Move the right edge forward so one more element joins the window.
shrink
Move the left edge forward so the oldest element leaves the window.
invariant
The rule your window must satisfy after every step, like 'exactly k numbers' or 'no repeated letters'.
fixed window
A window whose size is given (k). It always expands once and shrinks once per step.
variable window
A window whose size changes. It expands until the rule is met or broken, then shrinks until it is fixed or as small as it can be.

Watch it run

Step with → or Next. When a question pops up, make your guess. Try your own input once the guided run ends.

Getting the demo ready…

Recognise it

Most of the skill is noticing the clue in the problem statement.

Reach for it when

  • Yes: The problem says contiguous, subarray or substring.
  • Yes: A window size is given: "of size k" or "k consecutive".
  • Yes: It asks for the longest or shortest stretch such that some condition holds.
  • Yes: Brute force would re-check overlapping ranges again and again.

Not this when

  • No: The elements don't have to be next to each other (subsequences, pairs anywhere): think hash maps or dynamic programming.
  • No: You need to compare pairs from both ends of a sorted array: that is two pointers.
  • No: Numbers can be negative and the rule is "sum at least target": shrinking no longer lowers the sum, so reach for prefix sums with a monotonic deque.

Which pattern fits?

  1. Which pattern? 1 of 5

    Given an array of daily sales and a number k, return the largest total of any k consecutive days.

  2. Which pattern? 2 of 5

    Given a sorted array, find two numbers anywhere in it that add up to a target.

  3. Which pattern? 3 of 5

    Count the subarrays whose sum equals k. The numbers can be negative.

  4. Which pattern? 4 of 5

    Find the longest substring that contains at most 2 different letters.

  5. Which pattern? 5 of 5

    In how many different ways can you climb n stairs if each move is 1 or 2 steps?

The code

First the idea in plain steps. Then the same idea as real code, line for line.

Pseudocode
  1. 1window = 0, best = nothing yet, left = 0
  2. for each right from 0 to n - 1:
  3. 2add nums[right] to the window
  4. if the window holds more than k numbers:
  5. 3drop nums[left] and move left on
  6. if the window holds exactly k numbers:
  7. 4best = the better of best and the window
  8. 5return best

The faint numbers are the rules in the Rule Rail under the stage. Same numbers, same order.

Getting the replay ready…

def max_sum_k(nums, k):
    window = 0
    best = float('-inf')
    left = 0
    for right in range(len(nums)):
        window += nums[right]
        if right - left + 1 > k:
            window -= nums[left]
            left += 1
        if right - left + 1 == k:
            best = max(best, window)
    return best
Time · O(n)Space · O(1)
  • Each element is added once by right and dropped at most once by left, so the whole pass is at most 2n small steps: O(n).
  • For a variable-size window, turn the "too many?" if into a while loop. Keep shrinking until the rule holds again (or, for "shortest", until the window stops being big enough).
  • Space depends on the summary you keep: a running sum is O(1), a set or a count of letters grows with the window or the alphabet.
  • left and right only move forward. If you need to move one backwards, this isn't the pattern.

Worked examples

Real interview problems, solved with the same recipe.

Open on LeetCode (opens in a new tab)

Given an integer array nums and an integer k, find the contiguous subarray of length k with the largest average, and return that average.

Input

nums = [1,12,-5,-6,50,3], k = 4

Output

12.75

Approach

  1. The window has a fixed size, so its average is just its sum divided by k. Compare sums and divide once at the end.
  2. Sum the first 4 numbers: 1 + 12 - 5 - 6 = 2. That is the best so far.
  3. Slide right: add the new number, subtract the one that left. The sums are 51 (12, -5, -6, 50) and then 42 (-5, -6, 50, 3).
  4. The best sum is 51, so the answer is 51 / 4 = 12.75.
def find_max_average(nums, k):
    window = sum(nums[:k])
    best = window
    for right in range(k, len(nums)):
        window += nums[right] - nums[right - k]
        best = max(best, window)
    return best / k
Time · O(n)Space · O(1)

Knowledge check

Test yourself first. Try to answer these in your own words, then take the quiz below to check.

  1. Why is a sliding window faster than re-adding every stretch from scratch?
  2. A window of size 3 slides one step to the right. What changes?
  3. There is a while loop inside the for loop. Why is the sliding window still O(n)?
  4. For "shortest subarray with sum at least target" (positive numbers), when do you shrink?
  5. Which of these is a poor fit for a plain sliding window?

Question 1 of 5

Why is a sliding window faster than re-adding every stretch from scratch?

Assignment

Pick one, try it cold for ten minutes, then come back for the hint.

0 of 8 solved

  1. Solve Maximum Number of Vowels in a Substring of Given Length (opens in a new tab) (LeetCode, medium)

    Hint: The window size is fixed, so it is the same slide as the sum problem, but you keep a count of vowels instead of a sum.

  2. Solve Max Consecutive Ones III (opens in a new tab) (LeetCode, medium)

    Hint: Don't flip anything. Just look for the longest window that contains at most k zeros.

  3. Solve Fruit Into Baskets (opens in a new tab) (LeetCode, medium)

    Hint: It is the longest window with at most two different values, so keep a small count of each value and shrink when a third appears.

  4. Solve Longest Repeating Character Replacement (opens in a new tab) (LeetCode, medium)

    Hint: A window is fine when its length minus the count of its most common letter is at most k.

  5. Solve Permutation in String (opens in a new tab) (LeetCode, medium)

    Hint: A permutation has the same letter counts as the original, so slide a window of that exact length and compare counts.

  6. Solve Find All Anagrams in a String (opens in a new tab) (LeetCode, medium)

    Hint: Same fixed window as the permutation problem, but record every start index where the counts match instead of stopping at the first.

  7. Solve Minimum Window Substring (opens in a new tab) (LeetCode, hard)

    Hint: Expand until the window has every needed letter, then shrink while it still does, tracking how many letters are still missing.

  8. Solve Sliding Window Maximum (opens in a new tab) (LeetCode, hard)

    Hint: A running sum won't give you a maximum. Keep only the indices that could still become the maximum, in order, and drop the rest.

Additional resources