Day 5: Sliding Window Algorithm Explained
How to process data streams without starting over.
IN 30 SECONDS
The Sliding Window technique is a brilliant optimization for array or string problems that ask you to look at a "continuous chunk" (a subarray or substring). Instead of recalculating data from scratch for every single chunk, you create a "window," calculate the result once, and then simply slide the window over by removing the element that drops out the back and adding the new element that comes in the front.
THE REAL-WORLD ANALOGY
Imagine reading a long strip of paper through a small, square magnifying glass that can only fit 3 words at a time. To read the next 3 words, you don't pick up the glass and place it back down. You just slide it one inch to the right. One word leaves the left side of your view, and one new word enters the right side. The middle words never had to be re-read!
PICTURE THIS
Array: [2, 1, 5, 1, 3, 2], Window Size K=3\n\nStep 1: First Window\n[2 + 1 + 5] = 8\n\nStep 2: Slide Window Right\nOld: [2, 1, 5] (Sum: 8)\nRemove 2, Add 1\nNew: 8 - 2 + 1 = 7\nArray: 2, [1, 5, 1], 3, 2\n\nStep 3: Slide Window Right\nOld: [1, 5, 1] (Sum: 7)\nRemove 1, Add 3\nNew: 7 - 1 + 3 = 9
The diagram shows how sliding saves us from adding the middle numbers again. We just do one subtraction and one addition!
HOW IT ACTUALLY WORKS
- Initialize the Window: Compute the result (like a sum) for the very first window of size K.
- Slide: Move the window one position right.
- Update: Take the previous window's result, subtract the element that fell out of the left side, and add the element that entered the right side.
- Record: Keep track of the maximum or minimum value seen so far.
SHOW ME THE CODE
def max_subarray_sum(arr, k):\n if len(arr) < k: return 0\n \n # 1. Compute sum of first window\n window_sum = sum(arr[:k])\n max_sum = window_sum\n \n # 2. Slide the window from index k to the end\n for i in range(k, len(arr)):\n # 3. Add new element, subtract the old one\n window_sum += arr[i] - arr[i - k]\n \n # 4. Record the max\n max_sum = max(max_sum, window_sum)\n \n return max_sum
DRY RUN
Input: arr=[4, 2, 1, 7], k=2
| Step | Indices (Window) | Calculation | Current Max |
|---|---|---|---|
| 1 | 0 to 1 [4, 2] | Initial Sum: 4+2=6 | 6 |
| 2 | 1 to 2 [2, 1] | 6 - 4(out) + 1(in) = 3 | 6 |
| 3 | 2 to 3 [1, 7] | 3 - 2(out) + 7(in) = 8 | 8 (Updated!) |
SPEED & MEMORY
A naive approach checks every chunk from scratch, taking O(N * K) time. Sliding window does it in a single pass, dropping it to O(N). Because we only keep track of a few variables (the sum, the max), space is perfectly flat.
| Approach | Time | Space |
|---|---|---|
| Naive Nested Loops | O(N * K) | O(1) |
| Sliding Window | O(N) | O(1) |
WHERE YOU'LL SEE IT IN REAL LIFE
- Network Traffic: Calculating the average data transfer rate over the last 60 seconds of a continuous stream.
- Trading Algorithms: Computing the 50-day moving average of a stock price.
TRAPS TO AVOID
- Trap 1: Recomputing the entire window. Fix: Only add the new element and subtract the old one.
- Trap 2: Off-by-one errors in indices. Fix: The element dropping out is exactly at `i - k`.
- Trap 3: Array size smaller than K. Fix: Always add an edge case check at the start of your function.
PRACTICE
- Easy: Find the minimum sum subarray of size K.
- Medium: Find the longest substring with K unique characters. (Hint: Use a variable-size sliding window with a dictionary!).
TL;DR
- Sliding window optimizes continuous subarray problems from O(N^2) to O(N).
- It works by updating the result of the previous step rather than calculating from scratch.
- It comes in two flavors: Fixed Size (like our example) and Variable Size.
REFERENCES CONSULTED
Referenced for verification — all content above is original. Reviewed theory at GeeksforGeeks Sliding Window.
COVERED LOG UPDATE
Added: Day 5: Sliding Window