Back to Two Pointers and Sliding Window
Maximum Sum Subarray
Slide a fixed-size window of length k across the array. Update the sum in O(1) per step by removing the outgoing element and adding the incoming one.
Visualization
Speed
0
Current Sum
0
Max Sum
0–2
Window
0
2
1
1
2
5
3
1
4
3
5
2
Window [0..2] = [2, 1, 5]
Current windowMaximum window (final)Outside window
Ready — press Play or step through.
Complexity
O(n)
Time
O(1)
Space
O(k)
Initial Sum
O(1)
Per Slide
How It Works
- 1Compute the sum of the first k elements — this is the initial window sum and initial max
- 2Slide one step right: subtract the element leaving the left and add the element entering the right
- 3Update the maximum sum if the new window sum is larger
- 4Repeat until the window reaches the right end of the array
Applications
- •Finding the busiest k-hour window in server logs
- •Stock price analysis: best k-day gain window
- •Image processing: sliding average filters (box blur)
- •Network throughput: maximum bandwidth in any k-second window
Active Recall Quiz
Question 1 of 3
Why is the sliding window approach O(n) instead of O(n*k)?