What Is The Sliding Window Algorithm?

Intro

The sliding window algorithm is very appropriately named.

A sliding window (GIF here)

The benefit of a sliding window is that you can let in as much sun/air as you want, by opening up the window as wide or narrow as you want.

Suppose you have a linear data structure, such as an array or a list, but are only interested in a subsection of it. For example, given an array [1, 2, 3], one subarray would be [2, 3].

There are many interview questions that are asked, which involve subsections of an array. Luckily, many of these questions can be solved by using the sliding window algorithm.

Here is the sliding window algorithm:

1. Take an arbitrary subarray of the input array
2. Check if the subarray satisfies the question requirement
3. Expand or decrease the size or location of the subarray until the requirement is satisfied

We call it a sliding window since our subarray is essentially sliding along the input array, revealing only a subsection of the input array at any given time.

Let’s see a few examples.

Problem 1: Maximum Sum of Subarray

Given an array, and a size k, return the maximum sum of k contiguous elements.

Input:

int [] array = {4,2,1,7,8,1,2,8,1,0};
int k = 3

Output:

16

We get the output of 16 since 1 + 7 + 8 gives us the largest sum.

Strategy

As soon as you see the words “subarray” along with “contiguous”, you should immediately consider using the sliding window algorithm. Since the question specifies the size of the subarray, k , we know that our sliding window will not need to be resized.

Here’s a graphic that helps visualize the problem/solution:

Input: {4,2,1,7,8,1,2,8,1,0}
Window: {[4,2,1],7,8,1,2,8,1,0} Sum = 7
Window: {4,[2,1,7],8,1,2,8,1,0} Sum = 10
Window: {4,2,[1,7,8],1,2,8,1,0} Sum = 16
Window: {4,2,1,[7,8,1],2,8,1,0} Sum = 16
Window: {4,2,1,7,[8,1,2],8,1,0} Sum = 11
Window: {4,2,1,7,8,[1,2,8],1,0} Sum = 11…