Understanding the Sliding Window Technique in Algorithms

Annie Liao
Level Up Coding
Published in
3 min readSep 29, 2020

--

Photo by R Mo on Unsplash

Aside from the two-pointer technique demonstrated in my previous post, I have been grokking another popular algorithmic mental model: the sliding window.

If you have never heard of the sliding-window technique, I strongly recommend watching this video tutorial before diving into the example below. Even if you don’t have 36 minutes to spare, be sure to watch the first 8 minutes, which contain multiple well-executed animations.

What is the sliding window technique?

As its name suggests, this technique involves taking a subset of data from a given array or string, expanding or shrinking that subset to satisfy certain conditions, hence the sliding effect.

via The Simple Engineer video

When can we use it?

Generally speaking, the sliding window technique is useful when you need to keep track of a contiguous sequence of elements, such as summing up the values in a subarray.

Here’s a classic example (courtesy of Colt Steele’s Udemy course):

Given an array of positive integers and a positive integer,
write a function that returns the
minimal length of a contiguous subarray,
where the sum is greater than or equal to the integer being passed in.
If there isn’t one, return 0.

And here are some test cases:

minSubArrayLen([2, 3, 1, 2, 4, 3], 7) // 2 -> [4, 3] is the smallest subarray
minSubArrayLen([3, 1, 7, 8, 62, 18, 9], 52) // 1 -> [62] is the smallest subarray
minSubArrayLen([1, 4, 16, 22, 5], 95) // 0

To implement the sliding window technique for this challenge, we need to first figure out the range of the window. In this case, we “open up” the window from the left.

Then, we need to store the sum of the values in the enclosed subarray/window, and compare it against the target integer.

If the sum meets the condition (greater than or equal to the integer), we record the length of the current window range and keep shrinking the window, as we need to find the minimal length.

--

--

Fullstack Developer: React with Rails. Currently exploring data structures, D3 visualization, and other front-end magic.