Fixed Sliding Window
Overview
The Sliding Window is a subset of the Two Pointers pattern, specifically designed to solve problems involving Subarrays or Substrings.
A Fixed Sliding Window is used when the problem asks you to analyze a subarray of a specific, unchanging size (e.g., 'Find the maximum sum of any 3 consecutive elements').
A naive approach would use nested loops: for every element, start an inner loop to add the next 3 elements (O(NK) time). The Sliding Window approach realizes that as the window moves one step to the right, almost all the data remains exactly the same! You simply subtract the element that fell out of the left side of the window, and add the new element that entered the right side. This drops the time complexity to a strict O(N)*.
Syntax
public class FixedSlidingWindow {
// Find the maximum sum of any contiguous subarray of size K
public static int maxSumSubarray(int[] arr, int k) {
if (arr.length < k) return -1; // Edge case
int maxSum = Integer.MIN_VALUE;
int currentWindowSum = 0;
for (int i = 0; i < arr.length; i++) {
// 1. Add the newest element to the window
currentWindowSum += arr[i];
// 2. Only check sums and slide if we've hit window size K
if (i >= k - 1) {
// Record the maximum seen so far
maxSum = Math.max(maxSum, currentWindowSum);
// Slide the window forward by subtracting the oldest element
// The oldest element is at index (i - (k - 1))
currentWindowSum -= arr[i - (k - 1)];
}
}
return maxSum;
}
}Common Pitfalls
- Off-by-one errors in window sizing. The formula to find the oldest element leaving the window is
i - (k - 1). If you accidentally doi - k, you will subtract an element that is still supposed to be inside the window, destroying your calculations. - Recalculating the entire window. The whole point of this pattern is to AVOID recalculating. If you have an inner
forloop inside your window logic calculating the sum from scratch every time, you have failed to implement the pattern and are running in O(N*K) time. - Failing to handle arrays smaller than K. If
arr.length < k, the window can never form. If you don't check for this edge case at the start of the method, your math will break or return incorrect defaults.
Interview Questions
Look for three keywords in the prompt: 1) 'Contiguous', 'Subarray', or 'Substring'. 2) A specific size or length constraint 'K'. 3) A requirement to find a maximum, minimum, or average.
O(N). The algorithm processes every element in the array exactly once. Adding to the window is an O(1) operation, and subtracting from the window is an O(1) operation.
Real-World Example
Network Traffic Rate Limiting. A server allows a maximum of 100 requests per 1-second rolling window. A sliding window algorithm continuously adds new incoming requests to a counter, and subtracts requests that fall outside the 1000ms window, allowing the server to instantly reject traffic spikes in O(1) real-time.
// Conceptual Rate Limiting
int currentRequests = 0;
// Add new request
currentRequests += newRequestSize;
// Subtract requests older than 1 second
currentRequests -= oldRequestsLeavingWindow;
if (currentRequests > LIMIT) {
throw new RateLimitExceededException();
}Check Your Knowledge
Test your understanding of Fixed Sliding Window with these quick questions.