Sliding Window Visualization
Find the maximum sum of any contiguous subarray of size k.
Window Size (K):
Ready to start
Ready
Speed
Pseudocode
1function maxSum(arr, k)
2 currentSum = 0
3 for i = 0 to k-1
4 currentSum += arr[i]
5 maxSum = currentSum
6
7 for i = k to n-1
8 currentSum += arr[i] - arr[i-k]
9 maxSum = max(maxSum, currentSum)
10
11 return maxSum
Time Complexity
Brute ForceO(n*k)
Sliding WindowO(n)
Why it works:
Instead of recalculating the sum of the entire window every time (which takes O(k)), we simply subtract the element going out and add the element coming in (O(1)).