The sliding window technique is used to eliminate travel waste (nested loop) within an array whenever you need to operate on subarrays of length K.
This technique allows you to convert a time complexity of
O(N * K) to a single linear pass of
With a brute force solution, you’d use two loops, where the outer loop increments the subarray starting point, and the inner loop sequentially adds K elements to build the subarray. All of the inner loop’s work is lost/reset when the outer loop increments to the next starting element.
This results in unnecessary repetition: re-iterating over all of the prior subarray’s elements between the first and last; these are common between adjacent subarrays.
Instead of building a new subarray from each starting element, you can create the next subarray by performing two modifications to the current one:
- remove prior subarray’s first element from current subarray.
- add the next array element to current subarray.
This operation is a bit like an inchworm, inching along the parent array.
I’ve been looking for a way to physicalize algorithms for a while, and came across a video of a CS professor who simply used Legos.
Here’s an animation I made of a trivial and contrived array search (find any subarray of length 4), comparing a brute force approach to a sliding window approach.
You can easily see the improved efficiency:
The basic sliding window
Goal: Given an array, get a list of averages for each subarray of length K.
- Take an array
arrand a subarray length
- Init a container for your
results, to store the averages of each subarray.
- Init an intermediary accumulator value
sum, to store the sum of elements in the current subarray.
- Init a counter
windowStart, representing the index of the start of the sliding window.
- For each element at index
windowEndin the array,
- } Add the element to the accumulator.
- } If we have a complete subarray (
windowEndis greater than
- } } Calculate and append result for this subarray.
- } } Remove the element at
- } } Increment
windowStartto next index.