DSA · Chapter 7 of 40
Sliding Window
A sliding window keeps a contiguous range of the array or string and moves its right edge forward, shrinking from the left when a condition breaks. It answers questions about subarrays or substrings in O(n).
Fixed-size windows are used for averages and sums of k elements; variable-size windows are used for longest or shortest ranges satisfying a rule.
Fixed window
Add the incoming element and remove the outgoing one instead of recomputing the whole sum each time.
Variable window
Expand right while the window is valid; when it becomes invalid, move left forward until it is valid again, recording the best answer.
Example 1 (python)
def max_sum_k(nums, k):
window = sum(nums[:k])
best = window
for i in range(k, len(nums)):
window += nums[i] - nums[i - k]
best = max(best, window)
return best
print(max_sum_k([2, 1, 5, 1, 3, 2], 3))Output
9The window sum updates in O(1) per step.
Example 2 (python)
def longest_unique(s):
seen = {}
left = best = 0
for right, ch in enumerate(s):
if ch in seen and seen[ch] >= left:
left = seen[ch] + 1
seen[ch] = right
best = max(best, right - left + 1)
return best
print(longest_unique('abcabcbb'))Output
3A variable window finds the longest substring without repeats.
Key points
- Sliding windows work on contiguous ranges only.
- Fixed windows update in O(1) per move.
- Variable windows shrink from the left when invalid.
- Overall complexity is O(n) because each pointer moves forward only.
💡 Note: If the problem says subarray or substring plus longest/shortest/sum, think sliding window first.