Skip to content
Tutorials Center
My learning

Topics

Lesson 17 of 225 Ā· Arrays and Lists

Sliding Window

Learn the sliding window technique in Python with fixed windows (max sum of k), variable windows (longest substring without repeats), a reusable template and traces.

Many problems ask about contiguous stretches of an array or string: the best sum of any 3 consecutive days, the longest run of characters with no repeats, the shortest piece that contains everything you need. The direct approach recomputes each stretch from scratch, which wastes enormous effort because neighboring stretches overlap almost entirely.

The sliding window technique keeps one window over the data and updates it as it moves: add the item that enters on the right, remove the item that leaves on the left. The overlap is reused, and an O(n·k) or O(n²) solution becomes O(n).

The picture

A window is a range [left, right] of the array. It slides to the right one step at a time.

TEXT
data:   [ 2  1  5  1  3  2 ]      window size k = 3

step 1: [ 2  1  5] 1  3  2        sum = 8
step 2:   2 [ 1  5  1] 3  2       sum = 8 - 2 + 1 = 7
step 3:   2  1 [ 5  1  3] 2       sum = 7 - 1 + 3 = 9
step 4:   2  1  5 [ 1  3  2]      sum = 9 - 5 + 2 = 6

Each step: add the new item, subtract the item that fell off. One addition and one subtraction instead of re-adding k items.

There are two families. In a fixed-size window the width never changes. In a variable-size window the window grows and shrinks to satisfy a condition.

Fixed window: maximum sum of k consecutive items

Brute force. For every starting index, add up k items: n - k + 1 starts times k additions, so O(nĀ·k).

Sliding window. Compute the first window's sum once, then slide, updating by one add and one subtract: O(n) time, O(1) space.

Python Max sum of k consecutive items

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For 1,000 items and k = 100, the brute force does 90,100 additions while the window does 1,900 operations. The gap grows with k.

Do not slice inside the loop (sum(nums[i:i+k])). It looks tidy but it copies and sums k items every time, which is the brute force again.

Variable window: longest substring without repeating characters

Problem. Given a string, find the length of the longest substring in which all characters are different. For "abcabcbb" the answer is 3 ("abc").

Brute force. Check every substring for repeats: O(n²) substrings, each checked in O(n), giving O(n³), or O(n²) with early stopping.

Window idea. Expand right one character at a time. If the new character is already inside the window, the window is invalid, so shrink from the left until it is valid again. A set (or a dict of last positions) tells you quickly what is inside the window.

TEXT
s = "abcabcbb"
right=0 'a'  window "a"        len 1
right=1 'b'  window "ab"       len 2
right=2 'c'  window "abc"      len 3   <- best so far
right=3 'a'  'a' repeats: drop left 'a' -> "bca"   len 3
right=4 'b'  'b' repeats: drop 'b' -> "cab"          len 3
...

Each character enters the window once and leaves at most once, so the total work is O(n) even though there is a while inside the for. That is a very common source of confusion: nested loops do not always mean O(n²). See Analyzing Loops and Code.

Python Longest substring without repeats

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The answer for "pwwkew" is 3 ("wke"). Note that "pwke" is a subsequence but not a substring; windows are always contiguous.

The general template for variable windows

Most variable-window problems share one skeleton:

TEXT
left = 0
for right in range(len(data)):
    add data[right] to the window state
    while the window is invalid (or, for "shortest", while it is valid):
        remove data[left] from the window state
        left += 1
    update the answer using right - left + 1

Two flavors:

  • Longest window satisfying a rule: shrink while invalid, update the answer after shrinking.
  • Shortest window satisfying a rule: shrink while valid, update the answer inside the loop before removing.

The pre-condition for the shrink step to be correct is monotonicity: if a window is valid, making it smaller keeps it valid (or the reverse for the other flavor). With negative numbers in a "sum at least K" problem this breaks, and you need prefix sums plus other tools instead.

Variable window: shortest subarray with sum at least target

Problem. Given positive integers nums and a target, find the length of the shortest contiguous subarray whose sum is at least target; return 0 if none.

Because all numbers are positive, growing the window increases the sum and shrinking decreases it. Expand right; whenever sum >= target record the length and shrink from the left as far as the condition holds.

Python Smallest subarray with sum at least target

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Window with counts: at most k distinct characters

When the rule involves counts, store them in a dict. Here: the longest substring with at most k distinct characters. When a count drops to zero, delete the key so len(counts) equals the number of distinct characters.

Python Longest substring with at most k distinct characters

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Minimum window: the idea

A harder cousin is the minimum window substring: given strings s and t, find the shortest part of s that contains every character of t (with multiplicity). The same skeleton applies. Keep a count of how many characters of t are still missing; expand right until nothing is missing (valid), then shrink left while it stays valid, recording the smallest window. Use a dict for the needed counts and one integer, missing, so checking validity is O(1) rather than comparing two dicts each step. Try writing it yourself with the shortest-window template above. The total work is O(len(s) + len(t)).

Complexity

Problem Brute force Sliding window Space
Max sum of k items O(nĀ·k) O(n) O(1)
Longest unique substring O(n²) to O(n³) O(n) O(min(n, alphabet))
Shortest subarray, sum >= target O(n²) O(n) O(1)
At most k distinct O(n²) O(n) O(k)

Each index is added once and removed at most once, so the window does at most 2n pointer moves.

A sorted window: chocolate distribution

Sometimes the window is not over the original order. You have packets with different numbers of chocolates and must give one packet to each of m students so that the difference between the largest and the smallest packet handed out is as small as possible. After sorting, any good choice is m consecutive packets, so slide a window of size m over the sorted array and take the smallest sizes[i + m - 1] - sizes[i].

Python Chocolate distribution

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Sorting costs O(n log n) and the window pass O(n). The idea generalizes: when a problem asks you to pick m items with minimal spread, sort first and the answer is a window.

Common mistakes

  • Using a window on data with negative numbers when the problem relies on "bigger window = bigger sum".
  • Updating the answer at the wrong time: for "longest", update after the window is valid; for "shortest", update while it is valid.
  • Forgetting to remove a key when its count reaches zero, so the distinct count stays wrong.
  • Off-by-one in the length: the window [left, right] has right - left + 1 items.
  • Recomputing from scratch (sum(nums[left:right+1])) inside the loop.

Check your understanding

Quick check Ā· 5 questions

of 5 answered You scored / 5 Ā· perfect!

  1. 1. Why is the sliding window solution for the max sum of k consecutive items O(n)?

    Neighboring windows overlap in k - 1 items, so updating the sum costs O(1) instead of O(k), and there are about n windows.
  2. 2. The longest-unique-substring code has a while loop inside a for loop. What is its time complexity?

    left only moves forward and never exceeds right, so across the whole run the while loop executes at most n times in total.
  3. 3. In the shortest subarray with sum >= target problem, when do you update the best length?

    For the shortest valid window, every moment the window is valid is a candidate, and you keep shrinking while it stays valid.
  4. 4. Why can the positive-numbers shrinking logic fail on arrays with negative numbers?

    The technique relies on a monotonic property of the window. A negative number can make a larger window smaller in sum, so you can't tell when to shrink.
  5. 5. What is the length of the window covering indexes left=2 through right=6?

    Both ends are included, so the length is right - left + 1 = 5.

Summary

  • A sliding window reuses the overlap between neighboring stretches: add the entering item, remove the leaving one.
  • Fixed window: maintain a running value and slide; O(n) instead of O(nĀ·k).
  • Variable window: expand right, shrink left while the rule is broken (longest) or still holds (shortest).
  • A while inside a for is still O(n) because each pointer only moves forward.
  • It needs a monotonic condition; with negatives, consider prefix sums.

Next: Prefix Sums and Difference Arrays