Track a range with a sliding window
Grow and shrink a window to solve substring and subarray problems in O(n).
- 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
kitems. Add the new right element, subtract the element that falls off the left. - Variable size: expand
rightone step at a time; while the window breaks a rule, shrink it from theleft. 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).
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))9
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.
Longest substring without repeats
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
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…