# Sliding Window Technique

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 `O(N)`.

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:

1. remove prior subarray’s first element from current subarray.
2. add the next array element to current subarray.

This operation is a bit like an inchworm, inching along the parent array.

## Visual example

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.

1. Take an array `arr` and a subarray length `k`.
2. Init a container for your `results`, to store the averages of each subarray.
3. Init an intermediary accumulator value `sum`, to store the sum of elements in the current subarray.
4. Init a counter `windowStart`, representing the index of the start of the sliding window.
5. For each element at index `windowEnd` in the array,
6. } Add the element to the accumulator.
7. } If we have a complete subarray (`windowEnd` is greater than `k-1`),
8. } } Calculate and append result for this subarray.
9. } } Remove the element at `windowStart` from `sum`.
10. } } Increment `windowStart` to next index.
11. Return `results`.

tags:

categories:

posted: