Simulating Sliding Windows with a Single Loop
An introduction to the Sliding Window technique, demonstrating how to process subarrays efficiently without using nested loops.
Moving Beyond Single Elements
Many interview problems ask you to find something within a contiguous sub-segment of an array, like "find the maximum sum of any 3 consecutive elements." The brute force approach uses nested loops, recalculating the sum every time. The optimal approach uses a single loop and a Sliding Window.
The Problem with Nested Loops
// Brute Force O(N*K)
for (int i = 0; i <= arr.length - 3; i++) {
int sum = arr[i] + arr[i+1] + arr[i+2];
}
This works, but it recalculates overlapping elements. If you calculate the sum of indices [0,1,2], and then move to [1,2,3], you are re-adding 1 and 2.
The Sliding Window Concept
Instead of recalculating, visualize a "window" of size 3 over the array. When the window slides one position to the right, you do two things:
- Add the new element entering the window on the right.
- Subtract the old element leaving the window on the left.
The Implementation
int windowSum = arr[0] + arr[1] + arr[2]; // Initial window
int maxSum = windowSum;
for (int i = 3; i < arr.length; i++) {
// Add new right element, subtract old left element
windowSum = windowSum + arr[i] - arr[i - 3];
maxSum = Math.max(maxSum, windowSum);
}
The Takeaway
The Sliding Window technique is a masterclass in optimization. By maintaining state across iterations and only adjusting the differences, you can reduce an O(N*K) nested loop algorithm into a highly efficient O(N) single loop algorithm.
It is an algorithmic pattern that involves creating a 'window' over a subset of an array or string, and sliding it across the data to perform calculations efficiently.
Nested loops recalculate overlapping data repeatedly, causing O(N*K) time complexity. Sliding window maintains the state and only calculates the changes, achieving O(N).
Problems involving contiguous subarrays or substrings, such as finding the max sum of K elements, or the longest substring without repeating characters.
A fixed window stays the same size (e.g., exactly 3 elements). A dynamic window expands and contracts based on specific conditions (e.g., sum must be less than 10).
By subtracting the value of the element that just left the left side of the window, and adding the value of the element that just entered the right side.