dsa / dsa-arrays-strings
22 mins
DSA Module 3: Sliding Window Pattern
Why This Matters: Sliding window avoids recalculating overlapping contiguous subarray sums.
## Sliding Window Mechanics
The **Sliding Window** pattern slides a window across contiguous subarrays, updating running computations in O(1) time per step.
```python
def max_sum_subarray(arr, k):
window_sum = sum(arr[:k])
max_sum = window_sum
for i in range(k, len(arr)):
window_sum += arr[i] - arr[i - k] # Slide: add new, drop old
max_sum = max(max_sum, window_sum)
return max_sum
```
MENTAL MODEL & MEMORY LAYOUT
SLIDING WINDOW (Size K=3): Step 1: [ 2 1 5 ] 1 3 2 => sum = 8 Step 2: 2 [ 1 5 1 ] 3 2 => sum = 8 + 1 - 2 = 7 Step 3: 2 1 [ 5 1 3 ] 2 => sum = 7 + 3 - 1 = 9 (Max)
COMMON PITFALLS TO AVOID
- Recalculating sum from scratch inside loop `sum(arr[i:i+k])` (reverts to O(N*K) time).
Fixed Window Sum Pattern
arr = [2, 1, 5, 1, 3, 2] k = 3 # Max sum is 9 (5 + 1 + 3)
Updates window sum in O(1) time per iteration.
CONCEPT MASTERY CHECKPOINT
How does a sliding window update its running sum when moving 1 position right?
NEXT RECOMMENDED LESSON
DSA Module 4: Linked Lists & Fast/Slow Pointers
Challenge: Return max sum of contiguous K elements using sliding window.