Python 3.11+
The examples use the standard Python syntax and containers supported by the browser Judge; the Sliding Window invariant is independent of a minor Python release.
Verify in Python docs(opens in a new tab)Pattern2 Practice1 Interview
Sliding Window
Maintain an incrementally updated contiguous range instead of recomputing every subarray. Learn its decision rule, maintained state, Python cost model, and transfer from a focused drill to a full Interview Problem.
Recognize it when
Consider Sliding Window when the prompt's constraints and required operations match this shape: Maintain an incrementally updated contiguous range instead of recomputing every subarray.
On this page · Represent One Contiguous Window
Checking your account…
Sign in to save your code and progress across devices. The lesson and problem statement remain public.
Sliding Window Code Labs
Represent One Contiguous Window
A window is one contiguous interval, usually [left, right]. Its stored summary must describe exactly those elements—no stale character, count, or sum from outside the boundaries.
Expand Then Restore Validity
Add the new right element first. For a variable window, shrink left while the constraint is violated; only then measure a valid candidate. This order separates state updates from answer updates and prevents invalid windows from becoming the best.
Slide a Fixed Window
Reference
def fixed_window_sums(values, width):
if width > len(values): return []
total = sum(values[:width])
result = [total]
for right in range(width, len(values)):
total += values[right] - values[right - width]
result.append(total)
return resultPractice
Implement fixed_window_sums(values, width). Return every contiguous sum of exactly width values; return [] when width exceeds the input.
Public tests
- Update one entering and leaving value
Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor
Track Incremental State
A sum changes by one entering and one leaving value. A frequency map changes by increment and decrement, deleting zero counts when distinct-key count matters. Avoid slicing the window inside the loop because each slice copies O(window size).
Find the Longest Bounded Window
Reference
def longest_window_at_most(values, limit):
left = total = best = 0
for right, value in enumerate(values):
total += value
while total > limit and left <= right:
total -= values[left]
left += 1
best = max(best, right - left + 1)
return bestPractice
Implement longest_window_at_most(values, limit). values contains nonnegative integers. Return the maximum contiguous window length whose sum is at most limit.
Public tests
- Expand and restore validity
Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor
Choose a Window or Prefix State
Use a sliding window when validity changes monotonically as boundaries move and the answer is contiguous. Use prefix sums for immutable range queries or negative-number sum constraints where shrinking is not monotone. Each element enters and leaves at most once, so the variable scan is O(n).
Explain It in an Interview
Say: “My state describes exactly this contiguous window. I expand right, shrink until valid, then measure.” Name why shrinking can never need a removed element again. Longest Unique-Character Window(opens in a new tab) uses a frequency state under this invariant.
Python Version Note
Complexity & Invariants
Interview bounds depend on the stated representation, input model, and real Python operations.
| Operation | Average | Worst | Interview note |
|---|---|---|---|
| Sliding Window decision loop | O(n) | O(n) | When every candidate segment has the same width, reuse the previous aggregate instead of recomputing each segment. Before appending a result, the rolling total contains exactly values[right - width + 1:right + 1]. |
Space
O(n) for the returned sums for the focused Slide a Fixed Window implementation.
Assumptions
- The first total covers exactly the first width values. Each slide removes the value leaving the window and adds the value entering it, so every appended total belongs to the requested contiguous window.
- The bound includes real Python operations; no repeated slicing, linear list membership, or hidden sorting is treated as free.
Invariants Worth Saying Aloud
- State the precise Sliding Window invariant before coding and preserve it after every update, traversal step, or recursive return.
- The maintained summary describes exactly the current half-open window.
- Each element enters and leaves at most once.
- When every candidate segment has the same width, reuse the previous aggregate instead of recomputing each segment. Preserve this property after every transition.
- Before appending a result, the rolling total contains exactly values[right - width + 1:right + 1]. Preserve this property after every transition.
When To Use Or Avoid Sliding Window
Use It When
- Use Sliding Window when the prompt exposes the ordering, monotonicity, recurrence, or constraint that makes this decision safe.
- Use it when the maintained summary describes exactly the current half-open window.
Choose Another Tool When
- Avoid Sliding Window when its decision rule cannot eliminate work or preserve the required state.
- Avoid forcing the label onto a prompt whose simpler direct scan already meets the constraints.
Common Pitfalls
These are the mistakes most likely to survive a happy-path example and fail a boundary case.
Moving state without a proof
Applying the pattern without proving its ordering, monotonicity, or window invariant can silently miss valid candidates.
Prevent it: Write the decision rule beside the loop and verify it against Slide a Fixed Window before optimizing.
Avoid
def fixed_window_sums(values, width):
passUse instead
def fixed_window_sums(values, width):
if width > len(values):
return []
total = sum(values[:width])
result = [total]
for right in range(width, len(values)):
total += values[right] - values[right - width]
result.append(total)
return resultWhere you will hit this: Slide a Fixed Window(opens in a new tab)
Breaking the maintained state
Emits trailing partial windows after the last complete fixed-width segment.
Prevent it: Use the public tests and preserve this state: The maintained summary describes exactly the current half-open window.
Avoid
def fixed_window_sums(values, width):
return [sum(values[start:start + width]) for start in range(len(values))]Use instead
def fixed_window_sums(values, width):
if width > len(values):
return []
total = sum(values[:width])
result = [total]
for right in range(width, len(values)):
total += values[right] - values[right - width]
result.append(total)
return resultWhere you will hit this: Slide a Fixed Window(opens in a new tab)
Hiding Python work in the hot path
Python slicing, copying, membership in lists, or repeated sorting inside the loop can invalidate the intended complexity.
Prevent it: Count every slice, copy, sort, membership check, and container update before claiming O(n).
Avoid
def fixed_window_sums(values, width):
return [sum(values[start:start + width]) for start in range(len(values))]Use instead
def fixed_window_sums(values, width):
if width > len(values):
return []
total = sum(values[:width])
result = [total]
for right in range(width, len(values)):
total += values[right] - values[right - width]
result.append(total)
return resultWhere you will hit this: Longest Unique-Character Window(opens in a new tab)
Reviewed References
Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.
- Python deque Recipes(opens in a new tab)
python-docs · checked 2026-07-27