Frequently Asked Interview Problems – Sliding Window Maximum

1 min read

Hola CodeCheffers! Interviews and campus placements have already started for many, and now is the apt time for you to go through a few of the essential frequently asked questions by top-notch companies. This is the very first blog in the upcoming series where we can understand and learn these questions, and an expert will also explain these in detail. Here we will have a look at one of the very challenging questions – The Sliding Window Maximum.

What Is the Sliding Window Maximum?

You are given an array of size $N$. A sliding window of size $K$ starting from index 0 will also be mentioned in the question. Your task is to find the maximum value in the sub-array of elements. Let us take a look at one example. 

Let the input be { 2 4 8 9 1 6 7 }

So here, the number of elements is 7, and we can assume the window size to be 3. Thereby $N=7$ and $K=3$.

1st window : { 2 4 8 }; output=8

2nd window: { 4 8 9 }; output=9

3rd window: { 8 9 1 }: output=9

4th window: { 9 1 6 }; output = 9

5th window: { 1 6 7 }; output=7

Therefore the output is 8 9 9 9 7 

We can observe that the number of iterations or the number of sliding windows required is $N+K-1$.

How Do We Solve The Problem?

There are multiple ways to approach this problem, and we will look at two of them.

The Self Balancing BST

The Data Structure that can be made use of here is the Red-Black Tree. The Red-Black Tree automatically adjusts its height for every insertion and deletion in an average of $O(\log{}n)$ time. So for each window of size k using BST, we can insert the next element and remove the first element in each sub-array. 

  1. To implement self-balancing BST in the array first, you would have to create a self-balancing BST for the first k elements. The maximum of this subarray is computed and stored in another solution array. 
  2. Now to slide or move forward the window, we need to drop the first element (i.e., arr[i]) and insert the next element ( arr(i+k)). Now we have the 2nd window, and the maximum is again computed. 
  3. We can iterate through the whole array from 0 to n-k+1 element.

Deque method

Double Ended Queue or deque is the most optimal solution to this problem. Not all elements in the array need to be retained while iterating since some would never be a maximum element. The deque will keep the indices of the element and discard the ones that aren’t useful. 

For example, consider the array { 3 1 4 5 8 1 } and the window size is 3. The first iteration would be { 3 1 4 }, and the maximum element would be 4. Now for the next iteration, we need to append the next number, which is 5. Using the dequeue method will remove the elements smaller than the current array element, and the maximum element’s index would be in the front of the queue. 

Now that you have understood a few of the approaches, scoot and watch the YouTube video for a much detailed explanation from Saptarshi Mukherjee, an incoming SDE at Google. 

Well, that’s all for the time being from Ganga. Adios Amigos!

What Skills Do You Need To Work At Elon…

Heyya there! SpaceX has been generating quite a buzz, and you would have surely heard of this company. But have you ever thought of...
ganga4518
2 min read

The Second September Starters Didn’t Disappoint!

Starters 12 put up quite a show last night, and here’s us bringing you the whole lowdown. From a stunning ranklist to an equally skillfully...
debanjan321
1 min read

Rising Stars | September Long Challenge

We kick-started September with the lengthy Long Challenge, and there are so many more contests coming up for you soon. The Chef kept a...
ganga4518
1 min read

Leave a Reply