Sliding Window Foundations

8 concept walkthroughs, each with a worked explanation and an interactive visualization, before you start solving problems in this area.

A window is a slice of a row

A list is a row of boxes, and each box holds one value. Picture a shelf with five parcels that weigh 4, 2, 7, 1 and 6. Each box has an index, which is its position number. Counting starts at 0, because the index says how many boxes you step past from the start, and the first box needs 0 steps. So nums[1] is 2, and len(nums), the number of boxes, is 5. A window is a stretch of boxes that sit side by side with no gap. The boxes at positions 1, 2 and 3 make the window [2, 7, 1]. We name its two ends left and right, and both ends are inside the window. Python cuts a window out with a slice, nums[left:right + 1]. The end of a slice is always left out, so we add 1 to keep the box at right. The size of the window is right - left + 1, which is 3 - 1 + 1 = 3. A run of side-by-side values is called a subarray when it sits in a list, and a substring when it sits in a text.

The intuition

Why use windows at all? Many questions ask about a stretch of things that sit together: the heaviest three parcels in a row, or the longest piece of a word with no repeated letter. A window describes any such stretch with just two numbers, left and right. It also tells you how many stretches there are. With n = 5 boxes and width k = 3, a window can start at position 0, 1 or 2, so there are 5 - 3 + 1 = 3 windows. In general there are n - k + 1. Whenever a question asks about side-by-side items and wants the longest, the shortest, the biggest total or a count, think window.

• An index is a box's position number, counting from 0. The last box of a list has index len(nums) - 1.
• A window is boxes side by side with no gap. Its two ends are left and right, and both are inside it.
• nums[left:right + 1] cuts the window out, because the end of a slice is left out.
• The size of a window is right - left + 1.
• A list of n boxes has n - k + 1 windows of width k.
• A run of side-by-side values is a subarray in a list and a substring in a text.

A real-world analogy

Lay a cardboard frame with a rectangular opening over a shelf of parcels. Whatever shows through the opening is the window. The frame's left edge is left, its right edge is right, and the parcels you can see are the window's values. You can only ever see parcels that sit side by side, never two parcels with one hidden between them. Sliding the frame one place along the shelf shows a new window. The shelf is the list, the opening is the window, and the hidden parcels are everything outside it.

nums = [4, 2, 7, 1, 6]          # five parcels, positions 0 to 4
left, right = 1, 3              # two names in one line: the window is positions 1 to 3
window = nums[left:right + 1]   # the end of a slice is left out, so add 1
print(window)                   # [2, 7, 1]
print(len(window))              # 3, the same as right - left + 1
print(sum(window))              # 10, sum adds every value: 2 + 7 + 1
print(len(nums) - 3 + 1)        # 3, how many windows of width 3 fit

The slow way: add every window again

Here is a question. A shelf holds six parcels that weigh 2, 1, 5, 1, 3 and 2. Which three side-by-side parcels weigh the most in total? The direct way is to take each window of width 3, add its weights from scratch, and keep the biggest total seen so far. The four windows are [2, 1, 5] = 8, [1, 5, 1] = 7, [5, 1, 3] = 9 and [1, 3, 2] = 6. The answer is 9. Now count the work as additions: 4 windows x 3 additions each = 12 additions. Programmers describe how the work grows with Big-O. It says how many steps the job takes as the list gets longer. Here the steps grow like n x k, so we write O(n x k) and read it as order n times k. Try 100,000 parcels with width 50,000. There are 50,001 windows, and each is added from scratch: 50,001 x 50,000 is about 2.5 billion additions. That is far too many to finish quickly.

The intuition

Look at how often each parcel gets added: positions 0 to 5 are added 1, 2, 3, 3, 2 and 1 times, 12 in all. The 5 at position 2 is added three times, and every time it is the same 5. We keep working out things we already knew. Neighbouring windows share most of their parcels: [2, 1, 5] and [1, 5, 1] share the 1 and the 5. Adding the shared parcels again is pure waste. Spotting the waste is the first step to removing it. The extra memory used here is only a few boxes, total, best and left, however long the shelf is. We say the extra space is O(1), which means it does not grow with the list.

• Brute force means trying every window and doing all the work for each one. It is correct but can be slow.
• Count work in steps: windows x width. Here 4 x 3 = 12 additions.
• Big-O says how the number of steps grows as the list grows. O(n x k) means steps grow like n times k.
• range(a, b) counts a, a + 1 and so on up to b - 1. The stop value is left out, just like the end of a slice.
• max(a, b) gives the larger of two numbers, so best = max(best, total) keeps the biggest total so far.
• O(1) extra space means a few variables, no matter how long the list is.

A real-world analogy

A shop assistant checks the combined price of three neighbouring items on a shelf. For every new position they clear the calculator and key in all three prices again, even though two of the prices were typed a moment ago. The shelf is the list, the three prices are the window, clearing the calculator is starting total at 0, and typing the same prices again is the repeated work we want to avoid.

def best_sum_slow(nums, k):          # def starts a function, return hands back its answer
    best = 0                         # biggest total so far (fine while every value is positive)
    for left in range(len(nums) - k + 1):   # range(4) gives 0, 1, 2, 3: every start
        total = 0
        for i in range(left, left + k):     # positions left up to left + k - 1
            total = total + nums[i]         # add this window from scratch
        best = max(best, total)             # keep the larger of the two
    return best

print(best_sum_slow([2, 1, 5, 1, 3, 2], 3))   # 9

Fixed window: add the newcomer, drop the leaver

Slide the window one place to the right and look at what changed. Going from [2, 1, 5] to [1, 5, 1] on the shelf 2, 1, 5, 1, 3, 2, the parcel 2 at position 0 has left, the parcel 1 at position 3 has arrived, and the 1 and the 5 in the middle have not moved. So there is no need to add the middle again: new total = old total + newcomer - leaver. That is 8 + 1 - 2 = 7. We add the first window from scratch once, which is 2 + 1 + 5 = 8. After that, each slide is one addition and one subtraction, however wide the window is. The width stays the same, so this is called a fixed-size window. The two ends, left and right, are called pointers: numbers that point at a position. In the code, right is the newcomer's position, and right - k is the leaver's position, the box that just dropped off the left edge.

The intuition

Why can we trust the shortcut? The middle parcels belong to both windows, so their combined weight is one fixed number. It is 8 - 2 = 6 whatever the middle is made of: 1 and 5, or 3 and 3. The new total is that same 6 plus the newcomer 1, which is 7. The cost is also easy to count. Every parcel is added once when it arrives and subtracted once when it leaves. That is about 2 steps per parcel, so the work is O(n) and the width k no longer matters. For 100,000 parcels and width 50,000: 50,000 additions for the first window plus 50,000 slides x 2 = 150,000 steps, instead of 2.5 billion.

• A fixed-size window keeps the same width k and slides one place at a time.
• Add the first window from scratch, once.
• On every slide: new total = old total + newcomer - leaver.
• The newcomer sits at right and the leaver sits at right - k.
• Each parcel enters once and leaves once, so the work is O(n), not O(n x k).
• Forgetting the subtraction is the most common bug: the total keeps climbing and stops describing the window.

A real-world analogy

A small hall holds exactly three visitors at a time. When a new visitor walks in, the oldest visitor must walk out. The guard keeps a running tally of the ticket numbers inside: add the ticket of the person entering, subtract the ticket of the person leaving. The guard never recounts the people who stay. The hall is the window, the entering visitor is the newcomer, the leaving visitor is the leaver, and the tally is the running total.

def best_sum_fast(nums, k):
    total = sum(nums[0:k])         # the first window, added once
    best = total
    for right in range(k, len(nums)):          # right = the newcomer's position
        total = total + nums[right] - nums[right - k]   # newcomer in, leaver out
        best = max(best, total)
    return best

print(best_sum_fast([2, 1, 5, 1, 3, 2], 3))    # 9

Growing and shrinking: a window with a rule

Sometimes the width is not given, because the width is the answer. In the word "pqrqsp", find the longest stretch of side-by-side letters with no letter twice. Keep a window and one rule: no letter appears twice inside. Grow by moving right one place and taking in the new letter. If that letter is already inside, the rule is broken, so shrink: move left forward, letting the oldest letters go, until the repeat is gone. To remember which letters are inside, use a set. A set holds each value at most once and answers "is it in here?" in about one step on average. inside = set() makes an empty one, inside.add("p") puts p in, "p" in inside gives True or False, and inside.remove("p") takes it out. To repeat "until", we need a while loop: the lines under while run again and again for as long as its condition is True, and the condition is checked before every round. Once the shrinking stops, the window obeys the rule again. That is the moment to record its size.

The intuition

Why shrink from the left, and why never step back? Say the new letter repeats an older copy. Every window that starts at or before that older copy and ends here holds both copies, so none of them can ever be valid, whatever letters come next. The left edge must move past the older copy, and it never needs to return. That is also why the speed is good. right makes n moves, and left makes at most n moves in all, so the total is at most about 2n steps: O(n). The while loop sits inside the for loop, but we do not multiply. We count how many moves the two edges make in total, and each edge only moves forward.

• A variable-size window grows by moving right, and shrinks by moving left while its rule is broken.
• The rule always holds right after the shrinking, so that is when the size is recorded.
• A set stores each value once: add, remove, and in (is it inside?).
• while repeats for as long as its condition is True. Use it, not if, because one shrink step may not be enough.
• Both edges only move forward, so the total work is O(n), not O(n x n).
• The size of the window is right - left + 1, and best keeps the biggest size seen.

A real-world analogy

People stand in a line for a group photo with one rule: no two people may wear the same colour of scarf. A new person arrives at the right end of the line. If someone already wears that colour, people leave from the left end one at a time until the clash is gone, and then the newcomer joins. The line is the window, the scarf colour is the letter, the people leaving from the left are left moving forward, and the number of people in the line is the size.

def longest_no_repeat(s):
    inside = set()                    # the letters now inside the window
    left = 0
    best = 0
    for right in range(len(s)):       # grow: look at the next letter
        while s[right] in inside:     # shrink while it is already inside
            inside.remove(s[left])    # the oldest letter leaves
            left = left + 1
        inside.add(s[right])          # now it is safe to add
        best = max(best, right - left + 1)   # the rule holds, so record the size
    return best

print(longest_no_repeat("pqrqsp"))   # 4

Counting what is inside: dict, need and have

A set says yes or no. Many windows need to know how many. For that we use a dict, short for dictionary: a table that pairs a key with a value, such as the letter n with the count 2. {} makes an empty dict, counts["n"] = 2 stores a pair, and counts["n"] reads it back. Reading a key that is missing is an error, so counts.get("n", 0) is safer: it gives 0 when the key is missing. "n" in counts asks whether the key is there, and del counts["n"] removes the pair. A dict finds a key in about one step on average, however big it is. Two dicts are equal when they hold the same pairs, in any order. Here is the question: does "banana" hold three side-by-side letters that are a rearrangement of "nan", meaning the same letters in any order? need = {"n": 2, "a": 1} is what we look for, and have is what the window holds now. We slide a window of width 3. Each slide adds the newcomer to have, subtracts the leaver, and asks: is have == need?

The intuition

Two piles of letters are rearrangements of each other exactly when every letter has the same count in both. Order does not matter, only counts. So we never compare letters in order. We compare two small tables. There is one trap. When a leaver's count falls to 0, delete the pair. Otherwise {"a": 2, "b": 0} would look different from {"a": 2}, though they describe the same letters. Each slide changes just two pairs. Comparing two dicts looks at the few letters they hold, at most 26 for the letters a to z, which is a fixed number. So the total work stays O(n).

• A dict pairs keys with values. d.get(key, 0) gives 0 for a key that is not there.
• Count up with have[ch] = have.get(ch, 0) + 1, and count down by subtracting 1.
• When a count reaches 0, delete the pair with del, so that equal windows compare as equal.
• need is what we look for, built once. have is what the window holds, updated on every slide.
• Two dicts are equal when they hold the same pairs, in any order.
• A slide changes only two pairs: the newcomer's count goes up and the leaver's count goes down.

A real-world analogy

A word game gives you a tray that holds exactly three letter tiles, and a card that says which tiles are wanted: two N and one A. After every move of the tray, a helper updates a tally sheet of what is on the tray now: add one for the tile that arrived, cross out one for the tile that left. The card is need, the tally sheet is have, the tray is the window, and matching the sheet to the card is have == need.

text = "banana"
need = {"n": 2, "a": 1}                   # the letters of "nan"
have = {}                                  # what the window holds now
k = 3                                      # the window width
for right in range(len(text)):
    have[text[right]] = have.get(text[right], 0) + 1   # the newcomer comes in
    if right >= k:                         # the window is too wide: one must leave
        leaver = text[right - k]
        have[leaver] = have[leaver] - 1    # the oldest letter goes out
        if have[leaver] == 0:
            del have[leaver]               # remove the pair at zero
    if have == need:
        print("match, window ends at", right)
        break                              # break leaves the loop

At least: shrink while the window still holds everything

Now the rule is "the window holds at least what we need", and we want the shortest window that does. Take the shop signs "BAXBAB" and the need of one A and two B: need = {"A": 1, "B": 2}. A window may hold more than that, so we cannot use ==. Instead we keep missing, the number of needed letters still absent. At the start it is len("ABB") = 3. When a letter arrives, we count it in have. If have[ch] <= need.get(ch, 0), the letter filled an empty place, so missing goes down by 1. A third B or an X does not lower it. When missing reaches 0, the window covers everything. Now we shrink, and we keep shrinking while it still covers. Each time we are inside the loop, the window is valid, so we record its size first. Then the leaver goes out. If its count drops below the need, missing goes back up and the loop ends.

The intuition

The longest-stretch window shrank when its rule broke and recorded after the shrinking. This one shrinks while the rule holds and records before each step. The difference is what the goal is. In the longest version, a valid window gets better by growing. In the shortest version, a valid window gets better by shrinking, so we squeeze it until it is about to stop working. The missing counter turns the question "does the window hold everything?" from a check of every letter into one number compared with 0. Both edges only move forward, so the work is again O(n).

• "At least" is different from "exactly": have may hold more than need.
• missing counts the needed letters still absent. The window covers everything when missing == 0.
• A letter lowers missing only if it fills an empty place: have[ch] <= need.get(ch, 0).
• For the shortest window, shrink while the window is valid and record inside the loop: best = min(best, size), where min gives the smaller of two numbers.
• A leaver whose count falls below the need raises missing and stops the shrinking.
• Repeated letters in need matter: "ABB" needs two B, not one.

A real-world analogy

You want a photo of a street that shows at least one A shop and two B shops. You stretch the frame to the right until every shop on your list is in view. Then you squeeze the left edge inwards for as long as everything on the list stays in view, noting the frame's length each time. When a listed shop would drop out, you stop squeezing and stretch right again. The frame is the window, the shop signs are the letters, and the list is need.

s = "BAXBAB"
need = {"A": 1, "B": 2}                  # the window must hold at least this much
have, missing, left, best = {}, 3, 0, len(s) + 1   # best starts longer than any window
for right in range(len(s)):
    have[s[right]] = have.get(s[right], 0) + 1      # the newcomer comes in
    if have[s[right]] <= need.get(s[right], 0):     # it fills an empty place
        missing = missing - 1
    while missing == 0:                             # the window covers everything
        best = min(best, right - left + 1)          # record BEFORE shrinking
        have[s[left]] = have[s[left]] - 1           # the oldest letter leaves
        if have[s[left]] < need.get(s[left], 0):    # a needed place became empty
            missing = missing + 1
        left = left + 1
print(best)                                         # 3

A rule from the counts: how many changes does this window need?

Here the rule is a small calculation on the counts. A row of lockers is labelled with letters, "AAXAABB", and you may change at most k = 1 label. After the changes, what is the longest run of one repeated letter? Look at one window. Keep its most common letter and change all the others. The number of changes is the size minus the count of the most common letter. The window "AAX" has size 3, and A appears 2 times, so 3 - 2 = 1 change. The window is valid when changes <= k. In code, max(have.values()) gives the biggest count in have, because .values() lists all the counts. The loop is the same as before: add the newcomer to have, shrink with while the window needs too many changes, then record the size.

The intuition

A rule does not have to be "no repeats" or "has everything". It can be any yes-or-no question you can answer from what is inside the window. Here the question is: size - most common count <= k? We never need to decide which letter to change to. The most common one is always the cheapest choice, so size - top is the least number of changes. The most common count is found by looking at no more than 26 counts, a fixed amount, so the whole job stays O(n).

• Changes needed = size of the window - count of its most common letter.
• The window is valid when changes needed <= k.
• max(have.values()) gives the biggest count in the dict.
• The loop is the same as before: add the newcomer, shrink with while the window is not valid, then record its size.
• A window of one letter needs 0 changes, so the shrinking never empties the window.
• Looking at up to 26 counts each time is a fixed cost, so the total stays O(n).

A real-world analogy

A row of lockers has been painted in different colours, and a painter has k pots of paint, enough to repaint k lockers. For any stretch of lockers, the cheapest plan is to keep the most common colour and repaint the others. The stretch is the window, the colours are the letters, the pots are k, and the number of lockers to repaint is the size minus the count of the most common colour.

def longest_with_changes(s, k):
    have = {}
    left = 0
    best = 0
    for right in range(len(s)):
        have[s[right]] = have.get(s[right], 0) + 1    # the newcomer comes in
        while (right - left + 1) - max(have.values()) > k:   # too many changes needed
            have[s[left]] = have[s[left]] - 1         # the oldest letter leaves
            left = left + 1
        best = max(best, right - left + 1)            # valid now, so record
    return best

print(longest_with_changes("AAXAABB", 1))   # 5

Keeping the biggest ready: the deque

New question: for every window of width 3, find the biggest value. On the shelf [6, 2, 4, 1, 5, 3] the answers are 6, 4, 5 and 5. Scanning every window costs n x k, so we keep the biggest ready instead. Here is the key idea. When a bigger number arrives, any smaller number earlier in the window can never be the biggest again, because the newcomer is bigger and stays in the window longer. So we drop it. What stays is a shortlist whose values go from big to small, and the front of the shortlist is the biggest value. We remove from the back when a bigger number arrives, and from the front when the biggest has slipped out of the window. A list is slow at the front, since nums.pop(0) moves every other value one place left. A deque (say "deck") is built for both ends. We bring it in with from collections import deque. dq.append(x) and dq.pop() work at the back, dq.popleft() works at the front, dq[0] is the first and dq[-1] is the last, each in one step. An empty deque counts as False, so "dq and ..." first checks that it is not empty. We store positions, not values, so we can tell when the front has left the window.

The intuition

Why is dropping safe? Take 2 and the newcomer 4 in the window [6, 2, 4]. The 2 is older, so it leaves the window first. And it is smaller, so while it is in the window the 4 beats it. The 2 can never be the answer, whatever comes next. The shortlist is therefore kept in decreasing order, and the front is always the maximum. The work is O(n). A while loop sits inside the for loop, but each position is added to the deque once and removed at most once, so the total is at most about 2n removals and additions. The deque never holds more than k positions.

• A deque is fast at both ends: append and pop at the back, popleft at the front. dq[0] is the front and dq[-1] is the back.
• An empty deque counts as False, so write while dq and ... to avoid reading from an empty deque.
• The deque holds positions, with the values going from big to small, so the front is the maximum.
• At the back: remove positions whose value is smaller than or equal to the newcomer, then add the newcomer's position.
• At the front: if the position is i - k or earlier, it has slipped out of the window, so popleft. At most one leaves per step.
• The answer is nums[dq[0]] once the window is full, that is when i >= k - 1. The total work is O(n).

A real-world analogy

Think of a queue of people waiting for a group photo, and the photographer always wants the tallest person in the frame. When a taller person joins at the back, every shorter person in the queue is sent away, because the taller one will stay in the frame longer. People also leave from the front when their turn in the frame runs out. The person at the front is always the tallest. The queue is the deque, height is the value, and leaving the frame is the front slipping out of the window.

from collections import deque
def window_maximums(nums, k):
    dq = deque()                       # positions, values going big to small
    result = []
    for i in range(len(nums)):         # i = the newcomer's position
        if dq and dq[0] <= i - k:      # the front has slipped out of the window
            dq.popleft()
        while dq and nums[dq[-1]] <= nums[i]:   # smaller or equal at the back
            dq.pop()                   # can never be the biggest again
        dq.append(i)
        if i >= k - 1:                 # the window is full
            result.append(nums[dq[0]]) # add to the end of a list; the front is the biggest
    return result
print(window_maximums([6, 2, 4, 1, 5, 3], 3))   # [6, 4, 5, 5]

All DSA learning paths