Sliding Window
Learn the sliding window technique for finding subarrays that satisfy a condition in O(n) time.
Sliding Window
The sliding window technique uses two pointers — left and right — to define a window over an array. The window slides forward, expanding or contracting based on a condition. It turns many O(n²) brute force problems into O(n) solutions.
The problem it solves
Problem: Find the maximum sum of any subarray of length k.
Array: [2, 1, 5, 1, 3, 2], k = 3
Brute force — O(n²): Check every possible subarray of length k:
[2,1,5] = 8
[1,5,1] = 7
[5,1,3] = 9 ← max
[1,3,2] = 6For each starting position, sum k elements. That is O(n × k).
Sliding window — O(n): Compute the first window, then slide forward — subtract the element leaving, add the element entering. No recomputation needed.
How it works
def max_sum_subarray(arr, k):
n = len(arr)
# compute first window
window_sum = sum(arr[:k])
max_sum = window_sum
# slide the window forward
for i in range(k, n):
window_sum += arr[i] # add new element entering
window_sum -= arr[i - k] # remove element leaving
max_sum = max(max_sum, window_sum)
return max_sum
arr = [2, 1, 5, 1, 3, 2]
print(max_sum_subarray(arr, 3)) # 9Each step — add the new element on the right, remove the old element on the left. The window always has exactly k elements.
Variable size window
Some problems need a window that grows and shrinks based on a condition — not a fixed size.
Problem: Find the length of the longest subarray with sum ≤ target.
def longest_subarray_sum(arr, target):
left = 0
window_sum = 0
max_length = 0
for right in range(len(arr)):
window_sum += arr[right] # expand right
# shrink from left until condition is satisfied
while window_sum > target:
window_sum -= arr[left]
left += 1
max_length = max(max_length, right - left + 1)
return max_length
arr = [1, 2, 3, 4, 5]
print(longest_subarray_sum(arr, 9)) # 4 → [1,2,3] or [2,3,4]The pattern
Every sliding window problem follows the same structure:
left = 0
for right in range(len(arr)):
# 1. expand — include arr[right] in window
# 2. shrink — while condition violated, move left forward
# 3. update answer — record result for current windowWhen to use sliding window
| Signal in the problem | Use sliding window |
|---|---|
| "subarray" or "substring" | Yes |
| "contiguous" elements | Yes |
| "maximum/minimum length" | Yes |
| "sum equals / at most / at least" | Yes |
| Fixed window size k | Fixed window variant |
| Condition on window contents | Variable window variant |
The sliding window pattern appears constantly in interviews. Once you recognize the signal words — subarray, contiguous, sum, longest — reaching for this pattern immediately puts you ahead.
Complexity
| Time | Space | |
|---|---|---|
| Fixed window | O(n) | O(1) |
| Variable window | O(n) | O(1) |
| Brute force | O(n × k) | O(1) |