[Intermediate] — A university-level introduction to the sliding-window pattern: what it is, why it exists, how it works, and how to implement it independently.
Before you start
- You should understand arrays and basic loops. See arrays if needed.
- You should know what a hash map is. See hash maps for the variant below.
- You should understand the two-pointer pattern. See two-pointers if needed.
What you will be able to do after this lesson:
- Define the sliding-window pattern and explain why it turns “recompute something over every contiguous subarray/substring” from O(n·k) or O(n²) into O(n).
- Implement fixed-size and variable-size sliding windows independently.
- Apply the pattern to classic problems like longest substring without repeating characters and minimum window substring.
- Explain the amortized O(n) analysis despite nested-looking loops.
Study route: read the motivation and mechanism first, trace the worked example by hand, then attempt the independent task before looking at the hints.
1. Why this pattern exists (real-world motivation)
Imagine you’re building a real-time analytics dashboard that needs to track the maximum sum of any 3-day window in a time series of stock prices. You could check every possible 3-day window:
# O(n·k) naive approach
max_sum = -inf
for i in range(len(prices) - 2):
window_sum = prices[i] + prices[i+1] + prices[i+2]
max_sum = max(max_sum, window_sum)That’s fine for a single query, but a dashboard needs to answer many questions: “maximum 3-day sum,” “minimum 5-day sum,” “average 7-day window,” etc. Each query recomputes the same sliding sums over and over.
The sliding-window pattern solves this: compute the first window’s sum once, then slide it one step at a time, updating the sum by adding the new element and subtracting the element that falls out. This turns O(n·k) into O(n) — each element enters and leaves the window at most once.
Codility’s course material calls this the “caterpillar method” — same technique (a front and back index, each only ever moving forward), different name — worth recognizing if it comes up under that label.
2. Definitions and terminology
| Term | Plain-English definition | Example / analogy |
|---|---|---|
| Sliding window | A contiguous subarray/substring that moves one element at a time, maintaining a fixed or variable size | A camera panning across a scene, one pixel at a time |
| Fixed-size window | Window size k is constant; slide it one step at a time, removing the element that falls out the back and adding the one that enters the front | A 3-day moving average in finance |
| Variable-size window | Window grows and shrinks depending on a condition — expand the right edge to include more, shrink the left edge when a constraint is violated | Longest substring without repeating characters |
| Amortized O(1) | The average cost per operation across a long sequence of calls, even though some individual operations are expensive | Resizing a dynamic array: most appends are O(1), but resizing is O(n) — amortized O(1) |
3. How it works — step by step
Fixed-size window
Window size k is constant; slide it one step at a time:
def max_subarray_sum(nums, k):
window_sum = sum(nums[:k]) # compute first window
best = window_sum
for i in range(k, len(nums)):
window_sum += nums[i] - nums[i - k] # add new, drop oldest — O(1) per step
best = max(best, window_sum)
return bestConcrete example: nums = [2, 1, 5, 1, 3, 2], k = 3
window [2,1,5] sum=8
^ ^ ^
slide: [1,5,1] sum=8-2+1=7
^ ^ ^
slide: [5,1,3] sum=7-1+3=9 <- best
^ ^ ^
slide: [1,3,2] sum=9-5+2=6
^ ^ ^
Variable-size window
Window grows and shrinks depending on a condition:
def length_of_longest_substring(s):
seen = set()
left = 0
best = 0
for right in range(len(s)):
while s[right] in seen: # constraint violated -> shrink from the left
seen.remove(s[left])
left += 1
seen.add(s[right])
best = max(best, right - left + 1)
return bestEach character is added to seen at most once and removed at most once across the whole run — that’s what keeps this O(n) despite the nested-looking while inside the for.
4. Implementation — complete runnable example
Runnable example: save as sliding_window_lab.py and run python3 sliding_window_lab.py. It uses only Python’s standard library and creates no external files.
def fixed_size_sliding_window(nums, k):
"""Maximum sum of any contiguous subarray of size k."""
if len(nums) < k:
return None
window_sum = sum(nums[:k]) # compute first window
best = window_sum
for i in range(k, len(nums)):
window_sum += nums[i] - nums[i - k] # add new, drop oldest
best = max(best, window_sum)
return best
def variable_size_sliding_window(nums):
"""Length of longest subarray with all unique elements."""
seen = set()
left = 0
best = 0
for right in range(len(nums)):
while nums[right] in seen: # constraint violated -> shrink from the left
seen.remove(nums[left])
left += 1
seen.add(nums[right])
best = max(best, right - left + 1)
return best
if __name__ == "__main__":
# Test case 1: fixed-size window
nums1 = [2, 1, 5, 1, 3, 2]
k1 = 3
result1 = fixed_size_sliding_window(nums1, k1)
print(f"nums={nums1}, k={k1} -> max sum {result1}")
assert result1 == 9, f"Expected 9, got {result1}"
# Test case 2: variable-size window
nums2 = [1, 2, 3, 1, 2, 3, 1]
result2 = variable_size_sliding_window(nums2)
print(f"nums={nums2} -> longest unique substring length {result2}")
assert result2 == 3, f"Expected 3, got {result2}"
# Test case 3: edge case - all unique
nums3 = [1, 2, 3, 4, 5]
result3 = variable_size_sliding_window(nums3)
print(f"nums={nums3} -> longest unique substring length {result3}")
assert result3 == 5, f"Expected 5, got {result3}"
print("sliding_window_lab: passed")Expected output:
nums=[2, 1, 5, 1, 3, 2], k=3 -> max sum 9
nums=[1, 2, 3, 1, 2, 3, 1] -> longest unique substring length 3
nums=[1, 2, 3, 4, 5] -> longest unique substring length 5
sliding_window_lab: passed
5. Why it’s O(n) despite nested-looking loops
The key insight: each element enters and leaves the window at most once across the entire run.
- In fixed-size windows, each element is added once (when it enters the window) and removed once (when it leaves the window).
- In variable-size windows, each element is added to
seenat most once and removed at most once.
This means the total number of operations is bounded by 2n, not n². The same amortized argument as dynamic array resizing: the loop looks nested, but the total work across the whole run is linear.
6. Related patterns and extensions
Sliding window maximum (harder variant)
Fixed window where the aggregate isn’t invertible, so it needs a monotonic deque instead of the add-one-drop-one update:
def sliding_window_maximum(nums, k):
from collections import deque
dq = deque() # stores indices, values decreasing
result = []
for i, num in enumerate(nums):
# remove indices out of window
while dq and dq[0] < i - k + 1:
dq.popleft()
# maintain decreasing order
while dq and nums[dq[-1]] <= num:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
return resultMinimum window substring (harder variant)
def min_window_substring(s, t):
from collections import Counter
need = Counter(t)
missing = len(t)
left = 0
min_len = float('inf')
min_start = 0
for right, ch in enumerate(s):
if ch in need:
if need[ch] > 0:
missing -= 1
need[ch] -= 1
while missing == 0: # window satisfies t
if right - left + 1 < min_len:
min_len = right - left + 1
min_start = left
left_ch = s[left]
if left_ch in need:
need[left_ch] += 1
if need[left_ch] > 0:
missing += 1
left += 1
return s[min_start:min_start + min_len] if min_len != float('inf') else ""7. Tradeoffs and limitations
- Fixed-size windows only work for invertible operations. The add-one-drop-one update assumes you can compute the new sum from the old sum, the new element, and the element that fell out. For non-invertible aggregates (max, min, median), you need a different data structure (deque, heap, etc.).
- Variable-size windows need careful condition handling. The
whileloop inside theforcan be confusing; understanding why it’s still O(n) is key. - Not all contiguous subarray problems fit this pattern. Some problems require checking every possible window (e.g., “find all subarrays with sum equals k”) — prefix sums are better there.
8. Check your understanding (self-assessment)
Attempt these without the note, then compare your reasoning below.
- Question: Given
nums = [1, 2, 3, 1, 2, 3, 1]andk = 3, trace through the fixed-size sliding window algorithm step by step. - Question: Why is the variable-size sliding window algorithm O(n) despite the nested-looking
whileloop? - Question: What happens if the input contains negative numbers? Does the fixed-size sliding window still work?
Answers — after your attempt
window [1,2,3] sum=6->window [2,3,1] sum=6-1+1=6->window [3,1,2] sum=6-2+2=6->window [1,2,3] sum=6-3+3=6->window [2,3,1] sum=6-1+1=6. Maximum is 6.- Each element is added to
seenat most once and removed at most once across the entire run. The total number of additions and removals is bounded by2n, so the total work is O(n) even though there’s a nested-looking loop. - Yes, the fixed-size sliding window still works with negative numbers. The add-one-drop-one update is still valid:
new_sum = old_sum - nums[i-k] + nums[i]. The algorithm doesn’t assume positivity.
9. Practice — independent task
Task: Implement a function longest_substring_without_repeating(s) that returns the length of the longest substring without repeating characters. Use the variable-size sliding window pattern. Test it with the following cases:
s = "abcabcbb"→ expected3(substring “abc”)s = "bbbbb"→ expected1(substring “b”)s = "pwwkew"→ expected3(substring “wke”)
Done when: your function returns the correct lengths for all test cases.
Practice problems
In the NeetCode 150 — solved and written up here:
- Best Time to Buy and Sell Stock (LeetCode #121) — the degenerate window: track the minimum so far.
- Longest Substring Without Repeating Characters (LeetCode #3) — grow on the right, shrink from the left the moment a repeat appears.
- Longest Repeating Character Replacement (LeetCode #424) — the window is valid while length minus the most frequent count is at most .
- Permutation in String (LeetCode #567) — a fixed-size window and a character-count comparison.
- Minimum Window Substring (LeetCode #76) — the hardest of the family: expand to satisfy, then contract to minimise.
- Sliding Window Maximum (LeetCode #239) — a monotonic deque — where this pattern meets monotonic-stack.
Not in the NeetCode 150 — worth doing on LeetCode directly, since they drill the window-validity predicate, which is the part that generalises:
- Minimum Size Subarray Sum (#209) — variable window on a numeric constraint; the cleanest drill of the pattern.
- Find All Anagrams in a String (#438) — fixed window, same counting as #567.
- Max Consecutive Ones III (#1004) — “at most zeros” is a window-validity predicate.
- Longest Substring with At Most K Distinct Characters (#340) — the general form the others specialise.
- Maximum Number of Vowels in a Substring of Given Length (#1456) — fixed window, minimal distraction.
Before moving on
You are done with this pattern when you can, closed-book:
- Distinguish a fixed-size from a variable-size window and say when each applies.
- Explain the amortised O(n) argument despite the nested-looking
whileinside afor. - Implement longest-substring-without-repeats independently.
- State which aggregates a fixed window can update in O(1), and which cannot.
Recap: A sliding window maintains a summary of a contiguous range and updates it incrementally as the range moves, turning O(n·k) recomputation into O(n). Fixed windows add the entering element and subtract the leaving one, which requires an invertible aggregate; variable windows grow the right edge and shrink the left when a constraint breaks. Each element enters and leaves at most once, which is the amortisation.
Next: fast-slow-pointers — two pointers moving at different speeds over the same structure — the third way to arrange the same two-index idea.
10. Related
- two-pointers — sliding window is a specialization where both pointers move in the same direction
- hash maps — used in variable-size windows for fast membership testing
- monotonic-stack — alternative for sliding window maximum
- algorithms — where the amortized O(n) framing comes from
- sliding-window — this note
11. Further reading
The pattern appears in many contexts beyond LeetCode:
- Time series analysis: moving averages, rolling statistics
- Network traffic monitoring: bandwidth usage over sliding time windows
- Genomics: sliding window alignment in sequence analysis
- Financial engineering: risk calculations over rolling periods
The core idea — maintain a summary of the current window and update it incrementally — is a fundamental algorithmic technique that appears whenever you need to process data in chunks that slide across a larger dataset.
Software engineering
Infrastructure & security
Computer science
Hardware & engineering