0x40Lesson 5 of 13

Track a range with a sliding window

Grow and shrink a window to solve substring and subarray problems in O(n).

20 min 5-question quiz 1 code exercise

By the end of this lesson you can

Recognize contiguous-range problems.
Expand and shrink a window while keeping its state up to date.
Solve longest-substring problems in linear time.

Many problems ask about a contiguous subarray or substring: the longest substring without repeats, the smallest subarray with a sum at least k, the maximum sum of k consecutive items. Checking every range is O(n²) or worse. A sliding window keeps a range [left, right] and updates its state incrementally as the edges move, so each element enters and leaves the window at most once.

Fixed and variable windows

Fixed size: the window always has k items. Add the new right element, subtract the element that falls off the left.
Variable size: expand right one step at a time; while the window breaks a rule, shrink it from the left. Record the best valid window as you go.

The window’s state - a running sum, or a dictionary of character counts or last-seen positions - is what makes each step O(1).

solution.py

1def max_sum_of_k(nums, k):
2    window = sum(nums[:k])
3    best = window
4    for right in range(k, len(nums)):
5        window += nums[right] - nums[right - k]
6        best = max(best, window)
7    return best
8
9print(max_sum_of_k([2, 1, 5, 1, 3, 2], 3))

Output

For “longest substring without repeating characters”, keep a dictionary of each character’s last index. When the new character was seen inside the current window, jump left past its previous position. The answer is the largest right - left + 1 seen. Because left only moves forward, the whole scan is O(n).

Key takeaways

Windows solve contiguous-range problems in O(n).
Fixed windows add one element and remove one; variable windows expand then shrink.
Keep the window’s state updated incrementally.

Lesson quiz

5 questions · pass with 4 correct · up to 50 XP

Passing this quiz completes the lesson and keeps your streak going. Questions you miss come back in review sessions later.

Practice: solve interview problems

Solve a classic interview problem in Python and run it against test cases. Aim for the optimal complexity, then check the edge cases. Exercises run locally in your browser.

Exercise 1

Longest substring without repeats

+25 XP

Read a string (it may be empty). Print the length of the longest substring that has no repeated characters. Use a sliding window for O(n) time.

abcabcbb
All the same
pwwkew
Repeat outside the window
Empty string

main.py

Loading editor…

Python runs in a sandboxed browser worker with a 60 second time limit. Its runtime loads from the Pyodide CDN; your code stays in this browser.

Questions about this lesson

Stuck? Ask. Figured something out? Share it. Explaining is one of the best ways to learn.

Loading posts…