Sliding Window

Sliding Window | Algoryva

First, the naive way

Recompute every window

Task: find the largest sum of any k consecutive elements. The direct way sums each window separately.

Consecutive windows share k − 1 elements. Window [2, 1, 5] and the next window [1, 5, 1] both contain 1 and 5, yet we add them up again from scratch.

python

def best_window_naive(a, k):
    best = None
    for start in range(len(a) - k + 1):
        s = sum(a[start:start + k])
        best = s if best is None else max(best, s)
    return best

Cost: O(n × k). If k is about n/2 that is roughly n²/2 additions.

Implementation

Fixed window in Python

Build the first window once, then slide.

Plan in plain steps

pseudocode

s = sum of the first k elements; best = s
for each i from k to n - 1:
    s += a[i] - a[i - k]
    best = max(best, s)

python

def best_window(a, k):
    s = sum(a[:k])
    best = s
    for i in range(k, len(a)):
        s += a[i] - a[i - k]
        best = max(best, s)
    return best

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

Reading the code

›sum(a[:k]) is the one O(k) step, done once.
›a[i] enters and a[i - k] leaves: that index is exactly k steps behind, so the window stays size k.
›We need k <= len(a); otherwise there is no window. Check that first in real code.

Worked by hand

The variable window by hand

Longest run with sum ≤ 8 in [3, 1, 2, 7, 4, 2, 1, 1, 5]. Positions are 0-indexed; the window is [left, right].

right	added	sum	shrink?	window	best
0	3	3	no	[0,0]	1
1	1	4	no	[0,1]	2
2	2	6	no	[0,2]	3
3	7	13	drop 3, 1, 2 → 7	[3,3]	3
4	4	11	drop 7 → 4	[4,4]	3
5	2	6	no	[4,5]	3
6	1	7	no	[4,6]	3
7	1	8	no	[4,7]	4
8	5	13	drop 4, 2 → 7	[6,8]	4

1
Grow while valid
Through index 2 the sum is 6, within 8, so the window just gets longer.
2
Shrink when broken
Adding 7 makes 13. Dropping 3, 1 and 2 from the left brings it to 7: the left pointer jumped forward three times, never backwards.
3
Record after each step
The longest valid window is [4, 2, 1, 1] with sum 8 and length 4.

Implementation

Longest subarray with sum at most S

Translate expand and shrink into a for over right and a while for shrinking.

python

def longest_at_most(a, S):
    left = total = best = 0
    for right, x in enumerate(a):
        total += x                       # expand
        while total > S:                 # shrink until valid
            total -= a[left]
            left += 1
        best = max(best, right - left + 1)
    return best

print(longest_at_most([3, 1, 2, 7, 4, 2, 1, 1, 5], 8))   # 4

Reading the code

›The for moves right exactly once per element; the while moves left forward only. Neither ever moves back.
›After the while, the window [left, right] is valid (sum ≤ S), so right - left + 1 is a candidate length.
›If a single element exceeds S, the while empties the window (left = right + 1) and the candidate length is 0. That is correct.

Implementation

Tracking contents: longest substring with at most k distinct letters

When the rule is about *what is inside* the window, keep a dictionary of counts. Shrink while there are too many distinct keys.

python

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

print(longest_k_distinct("eceba", 2))   # 3

Reading the code

›count holds how many of each letter are in the window. len(count) is the number of distinct letters.
›When a count reaches 0 we must del the key, otherwise len(count) would still count a letter that is gone.
›Shape is identical to the sum version: expand, shrink while invalid, record.

Worked problem

Smallest subarray with sum at least S

The problem

Given an array of positive integers and a target S, return the length of the shortest contiguous subarray whose sum is at least S, or 0 if none exists.

Positive numbers make growing a window increase its sum, so the one-way property holds.
Expand right until the sum reaches S; then the window is *valid*, and we try to make it smaller.
While valid, record the length and shrink from the left.

python

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

print(min_len_at_least([2, 3, 1, 2, 4, 3], 7))   # 2

Takeaway. Longest asks you to shrink while *invalid*; shortest asks you to shrink while *valid*. Decide which before writing the while.

Worked problem

Longest substring without repeating characters

The problem

Given a string, return the length of the longest substring in which no character appears twice.

Keep the last index where each character was seen.
Expand right. If the new character was seen at or after left, jump left to one past that earlier position.
Record right - left + 1 each step.

python

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

print(longest_unique("abcabcbb"))   # 3

Takeaway. A window can shrink by jumping, not just by one step, when you know exactly where the conflict is. last[ch] >= left ignores sightings that already fell out of the window.

Wrap-up

Remember this

A window keeps the answer for a contiguous range and updates it in O(1) as the range moves.
Fixed size: add the entering element, subtract the leaving one.
Variable size: expand right, shrink left while the rule is broken (or, for shortest, while it holds).
The variable window needs a one-way property; negative numbers usually break it.
Both pointers only move forward, so total work is O(n) even with a while inside a for.

Cheat sheet

Fixed window: s += a[i] − a[i − k]
Variable (longest): expand right; while invalid: shrink left; record
Variable (shortest): expand right; while valid: record, shrink left
Length: right − left + 1
Cost: O(n) time: left and right each move ≤ n
Needs: contiguous range + one-way validity

Top traps to avoid

Recomputing the window contents inside the loop.
Using an if instead of while to shrink.
Forgetting to delete a dictionary key when its count hits 0.

Mastery check

0 of 15 answered

Answer from understanding, not memory of the page. You need 12 of 15. Each answer is explained, and you can retry as often as you like.

1.Why is the variable sliding window O(n) even though it has a while inside a for?
2.For a = [2, 1, 5, 1, 3, 2] and k = 3, the window sums are 8, 7, 9, 6. What does the best window sum equal?
3.Which statement is best solved with a sliding window?
4.Why does “longest subarray with sum at most S” fail if the array has negative numbers?
5.When tracking character counts in a window, why delete the key when its count reaches 0?
6.min_len_at_least([2, 3, 1, 2, 4, 3], 7) returns:
7.What is the length of the longest substring of 'abcabcbb' with no repeated character?
8.For a = [2, 3, 1, 2, 4, 3] and target sum 7, what is the shortest subarray whose sum is at least 7?
9.What does a monotonic-deque sliding maximum of size 3 print for [1, 3, -1, -3, 5, 3, 6, 7]?
10.What is the longest subarray of [1, 2, 1, 2, 3] with at most 2 distinct values?
11.A sliding window has a while loop inside a for loop. Why is the total still O(n)?
12.A fixed window of size k over n values, with a running sum: what is the time?
13.When extending a window to find the longest valid window, when should the left end move?
14.Counting windows of size 2 whose sum is greater than 3 in [1, 2, 3, 4], how many are there?
15.What is the largest sum of a window of size 2 in [4, 2, 1, 7, 3]?

Sliding Window

After this lesson you will be able to

Builds on

Unlocks

A train window

Recompute every window

Next window = previous window + entering − leaving

Fixed-size window

Fixed window in Python

Reading the code

Windows whose size changes

Expand, then shrink

The variable window by hand

Longest subarray with sum at most S

Reading the code

Tracking contents: longest substring with at most k distinct letters

Reading the code

Why O(n)

Edge cases

Mistakes to avoid

How to spot a sliding window

Smallest subarray with sum at least S

Longest substring without repeating characters

Wrap-up

Remember this

Cheat sheet

Top traps to avoid

Mastery check

Practice this topic

Warm-up3 problems

Core5 problems

Application4 problems

Challenge1 problem