Sliding Window Technique in Python

The sliding window technique solves problems about contiguous stretches of an array or string (a “window”) by sliding that window along the data and updating its result a little at a time, instead of recomputing it from scratch. When the window moves one step, you add the new item on the right and remove the old one on the left. That turns an O(n × k) or O(n²) solution into O(n).

There are two flavours: a fixed-size window (for example “the best sum of 3 consecutive numbers”) and a variable-size window that grows and shrinks (for example “the longest substring with no repeated letters”). Both are below, with real output.

The idea

Suppose you want the largest sum of any 3 consecutive numbers in [2, 1, 5, 1, 3, 2]. The slow way adds up every group of 3 from scratch. But two neighbouring groups overlap almost completely. Moving from one to the next, you only need to add the new item and subtract the one that left:

nums = [2, 1, 5, 1, 3, 2]
k = 3
window = sum(nums[:k])
best = window
print("start", window)
for i in range(k, len(nums)):
    window += nums[i] - nums[i - k]
    best = max(best, window)
    print(f"add {nums[i]}, remove {nums[i - k]} -> {window}")
print("best", best)

Output

start 8
add 1, remove 2 -> 7
add 3, remove 1 -> 9
add 2, remove 5 -> 6
best 9

Instead of adding three numbers each time, every step was one addition and one subtraction. On a small list that hardly matters, but count the steps on 1,000 numbers with a window of 100:

def max_sum_brute(nums, k):
    best, steps = float("-inf"), 0
    for i in range(len(nums) - k + 1):
        total = 0
        for j in range(i, i + k):
            total += nums[j]
            steps += 1
        best = max(best, total)
    return best, steps

def max_sum_window(nums, k):
    window = sum(nums[:k])
    best, steps = window, k
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]
        steps += 1
        best = max(best, window)
    return best, steps

Steps for brute force, steps for the window (the answers agree)

90100 1000 True

The brute-force method took 90,100 steps and the sliding window took 1,000, and both gave the same answer. The gap widens as the window and the data grow.

Fixed-size windows

When the window has a set size k, the recipe is always: compute the first window, then slide, adding items[i] and removing items[i - k]. That is what max_sum_window does. Typical fixed-window questions: the maximum or average sum of k consecutive values, or how many windows of size k have a certain property.

Variable-size windows

Often the size is not fixed. You want the longest or shortest window that satisfies a rule. The window then grows to the right one item at a time, and shrinks from the left whenever it becomes invalid.

Longest substring without repeating characters

Here is the window moving across "abcabcbb". When the new character is already inside the window, the left edge moves right until the duplicate is gone:

s = "abcabcbb"
seen = set()
left = 0
for right, ch in enumerate(s):
    while ch in seen:
        seen.remove(s[left])
        left += 1
    seen.add(ch)
    print(right, ch, "window =", s[left:right + 1])

Output

0 a window = a
1 b window = ab
2 c window = abc
3 a window = bca
4 b window = cab
5 c window = abc
6 b window = cb
7 b window = b

The window never contains a repeated letter, and its longest length was 3 (abc, bca, cab). A faster version remembers the last position of each character so the left edge can jump straight past a duplicate:

def longest_unique(s):
    last_seen = {}
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best

print(longest_unique("abcabcbb"))
print(longest_unique("bbbbb"))
print(longest_unique("pwwkew"))
print(longest_unique(""))

Output

3
1
3
0

Smallest subarray with a sum of at least a target

Expand until the sum is big enough, then shrink from the left for as long as it still is. Each time it is big enough, record the length:

def min_len_subarray(nums, target):
    left = total = 0
    best = float("inf")
    for right, x in enumerate(nums):
        total += x
        while total >= target:
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1
    return 0 if best == float("inf") else best

print(min_len_subarray([2, 3, 1, 2, 4, 3], 7))
print(min_len_subarray([1, 1, 1], 10))

Output

2
0

For [2, 3, 1, 2, 4, 3] and target 7, the best window is [4, 3], of length 2. The inner while loop makes it look like O(n²), but it is not: left only ever moves forward, so across the whole run each item is added once and removed at most once. The total is O(n).

Both variable examples follow the same skeleton:

def variable_window(items):
    left = 0
    state = ...                      # running sum, counts, a set...
    best = 0
    for right, x in enumerate(items):
        add x to the state           # expand the window
        while the window is invalid:
            remove items[left] from the state
            left += 1                # shrink it
        best = max(best, right - left + 1)
    return best

More window problems

At most k distinct characters

Keep a dictionary of counts inside the window. When there are more than k different characters, shrink from the left until there are k again:

def longest_k_distinct(s, k):
    counts = {}
    left = best = 0
    for right, ch in enumerate(s):
        counts[ch] = counts.get(ch, 0) + 1
        while len(counts) > k:
            counts[s[left]] -= 1
            if counts[s[left]] == 0:
                del counts[s[left]]
            left += 1
        best = max(best, right - left + 1)
    return best

print(longest_k_distinct("eceba", 2))
print(longest_k_distinct("aa", 1))

Output

3
2

For "eceba" with k = 2, the longest valid window is "ece". (Dictionaries and counting are explained in Python Dictionaries Explained.)

Longest run of ones if you may flip k zeros

This is the same pattern again, with “number of zeros” as the thing the window tracks. If the count exceeds k, shrink. Try it yourself below.

A harder one: the maximum in every window

What if the window rule is “the maximum of the window”? You cannot subtract a maximum when an item falls out. The trick is to keep a deque of candidate positions whose values are in decreasing order. The front is always the current maximum:

from collections import deque

def window_max(nums, k):
    dq = deque()
    out = []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out

print(window_max([1, 3, -1, -3, 5, 3, 6, 7], 3))

Output

[3, 3, 5, 5, 6, 7]

Each index is added once and removed once, so it is still O(n). The deque type is described in Queue and Deque in Python Explained.

How to recognise a sliding window problem

Common mistakes

Mistake 1: recomputing the window every time

Summing items[i:i+k] inside a loop is the brute-force approach: O(n × k). Update the running value instead.

Mistake 2: using a sum-based window when the numbers can be negative

Shrinking the window is safe only when removing an item always makes the sum smaller. With negative numbers that is false, and the answer can be wrong. Here is the “smallest subarray with sum at least 5” function on [1, -1, 5]. The true answer is 1 (the single item 5), but the window version returns 3:

def min_len_subarray(nums, target):
    left = total = 0
    best = float("inf")
    for right, x in enumerate(nums):
        total += x
        while total >= target:
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1
    return 0 if best == float("inf") else best

nums = [1, -1, 5]
print(min_len_subarray(nums, 5))
print(min(len([x]) for x in nums if x >= 5))

Output

3
1

For arrays with negative numbers, other approaches (such as prefix sums with a dictionary) are needed.

Mistake 3: an off-by-one in the window length

The number of items in items[left..right] is right - left + 1. Forgetting the + 1 is the classic slip.

Mistake 4: forgetting to update the state when shrinking

Whenever left moves, the running sum, counts or set must lose items[left] first. Otherwise the window and its record drift apart.

Try it yourself

Work out each answer first, then open the solution.

1. Find the maximum average of any 3 consecutive numbers in [1, 12, -5, -6, 50, 3].

nums = [1, 12, -5, -6, 50, 3]
k = 3
window = sum(nums[:k])
best = window
for i in range(k, len(nums)):
    window += nums[i] - nums[i - k]
    best = max(best, window)
print(round(best / k, 2))

15.67

2. Given a list of 0s and 1s, find the longest run of 1s if you may flip at most k zeros.

def longest_ones(nums, k):
    left = zeros = best = 0
    for right, x in enumerate(nums):
        if x == 0:
            zeros += 1
        while zeros > k:
            if nums[left] == 0:
                zeros -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

print(longest_ones([1, 1, 0, 0, 1, 1, 1, 0, 1], 2))

7

3. Why is the variable-window solution O(n) even though it has a while loop inside a for loop?

Run these in our free Python compiler.

Frequently asked questions

What is the sliding window technique?

It is a method for problems about contiguous subarrays or substrings. You keep a window over the data and slide it forward, updating a running result (sum, count, set) as items enter and leave, instead of recomputing it for every position.

What is the difference between fixed and variable sliding windows?

A fixed window always has the same size k. A variable window changes size: it expands on the right and shrinks from the left depending on a condition, such as “no repeated characters”.

What is the time complexity of a sliding window?

Usually O(n), because each pointer only moves forward and every item enters and leaves the window at most once.

How is a sliding window different from two pointers?

It is a special case of two pointers. Both pointers move forward, and the range between them is a contiguous window whose contents you track.

When does a sliding window not work?

When the rule is not monotonic, for example a sum constraint on data that includes negative numbers. In that case, adding or removing an item can move the total in either direction, so shrinking is not safe.

Related reading

• Two Pointers Technique in Python – the parent technique.
• Queue and Deque in Python Explained – the deque used for window maximum.
• Hash Tables in Python: Dict and Set for DSA – counting items inside a window.
• 10 Coding Interview Patterns in Python – sliding window among the key patterns.