Topic 52 of 78
Fixed Sliding Window
Overview
The Sliding Window pattern is used to process continuous subarrays or substrings. In a 'Fixed' sliding window, the size of the subarray is strictly given (e.g., 'Find the max sum of any 3 consecutive elements'). Instead of calculating the sum from scratch for every group of 3 (O(N*K)), you calculate the sum of the first window, then simply slide the window forward by subtracting the element that left the window and adding the new element that entered it. This drops the complexity to O(N).
Syntax
By reusing the previous sum, we avoid repeating O(K) addition operations on every step. O(N) linear time!
Max Sum Subarray of Size K
java
public int maxSum(int[] arr, int k) {
if (arr.length < k) return -1;
int maxSum = 0, windowSum = 0;
// 1. Calculate the sum of the very first window
for (int i = 0; i < k; i++) {
windowSum += arr[i];
}
maxSum = windowSum;
// 2. Slide the window forward one element at a time
for (int i = k; i < arr.length; i++) {
// Add the new element, subtract the element left behind
windowSum = windowSum + arr[i] - arr[i - k];
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}Common Pitfalls
- Forgetting to check if the array length is actually larger than K before initializing the first window.
- Messing up the index of the outgoing element (`arr[i - k]`).
Interview Tips
- Whenever you hear 'Subarray of length K', immediately write down Fixed Sliding Window.
Real-World Example
Network traffic monitoring systems use fixed sliding windows to calculate average throughput or detect DDOS attacks over a strict 60-second window.
example
java
public double getAverageRequestsPerMinute(int[] requestsPerSecond) {
// Calculates a rolling average by sliding a 60-second window across the data stream
return maxRequests(requestsPerSecond, 60) / 60.0;
}