Maximum Element Sliding Window

A very interesting problem indeed! Often asked in Interviews in various forms and we will discuss one of these forms here in this post.

Problem Statement – Maximum Element Sliding Window

Given a stream or array of elements (preferably integers). Find the elements with maximum value in a window of length K where the window slides by one step to the right every time.

What is a Sliding Window?

Given an array A, a sliding window of length K is a range of fixed size K in the array such that the range slides to the right by one index. Here is a diagram to explain how sliding window will look like in a given array.

sliding1

The red outlined box is a window of length 3. This window slides one step at a time to the right. So, as per our problem definition, the window shown in :

  • The image labeled 1 has a maximum value 10, which is the maximum of (8, 5 and 10).
  • The image labeled 2 also has a maximum value 10, which is the maximum of (5, 10 and 7)
  • The image labeled 3 also has a maximum value 10, which is the maximum of (10, 7 and 9)
  • If we had more images of the next window then the maximum would have been 9, which is the maximum of (7, 9 and 4) and so on …

Now the solution to this problem, of course there is a brute force solution which is as follows:

Brute Force Solution

The idea is as follows:

  • Loop through the first array such that the loop runs from the beginning of the array till the (end – window) size
  • For each index of the loop, iterate from current index and move right till the window length to find the new maximum.
  • Return the new maximum.

Clearly it looks to be a O(N.w) running time solution. For each element in the array, the inner loop travels for the length of the window.

Can we do better?

Well the answer is YES, and we can achieve it by some trade-offs. The solution I am trying to describe is an O(N) solution but it also requires additional space.

We can use a DeQueue ( a doubly ended queue) or an ArrayList in Java. Here is the idea:

Step 1: For the first window 0 to w, start from i = 0, add the index i into the queue, and move right. Two conditions arise:

  • The element at the next index (i+1) is greater than the element at the end of the queue, in this case keep removing the last element from the queue until the queue is empty or the element at the end gets greater than this current element.
  • The element at the next index is smaller than the element at the end of the queue, in this case proceed to next step.

Step 2 : Add the next index to the end of the queue.

Once this is done, there is a sliding involved where we need to assess the new element as per the above guidelines and then remove the first element from the queue, if it lies in the range of the window.

Execution Steps and Explanation

Here is a diagrammatic explanation for the same. Let us consider the below array. The area shaded in light green is the array and the area in light purple is the queue.

For the first window (index 0 – 2)

When we start from index 0, that is the maximum we know and hence, we add it to the queue.
But as we move right we find 7 at index 1, we add it to the end of the queue. You must be wondering why do we push 7 if we already have 8 which is max of 8 and 7.

This is because sometime in the future when we slide the window to the right, there will be a time when 8 will not fall in the range and at that time 7 might be the maximum in that range. So, we need to keep track of all elements smaller than the last element in the queue.

Now when we move further right, we notice that this is the boundary of the window and the element at that point is 6, which is again smaller than the last element of the queue, hence we add it to the end of the queue  as we did the last time.

Maximum Element Sliding Window

 

Sliding by one step (index 1-3)

Now we slide the window to remove 8 from the window range and add 5 to it. We find that 5 is smaller than the last element in the queue. Hence, by the same argument we add 5 at the end of the queue, but at the same time we remove 8 from the queue, as it is out of the range now.

Sliding by one more step (index 2-4)

This time we get a 10 which is greater than the element at the end of the queue which is 5, hence it is certain that a range containing 5 and 10 will have maximum as 10 because 10 comes after 5 in the array. So, we can get rid of 5.

We can further evaluate for other element at the end of the queue (which is 6) and then 6 is smaller than 10 hence we can get rid of 6 as well by the same argument.

So now the queue only contains 10. And at each step the first element in the queue gives the max in the range from index i to i+w.

Source Code

Analysis

The running time of the algorithm might seem to be more than linear time O(N) but in reality it isn’t. If you see the code within the inner loop, we see that each while loop modifies the queue and the queue contains each element of the array only once.

Hence, all the iterations of the outer loop combined together will be able to just perform N additional addition operations and N removal operations. So, the running time would be a max of O(N), you may say it 2N or 3N but in terms of Big O, it is O(N)

Talking about the space complexity, you may end up using a space O(N) in the worst case. If all the elements in the array are reversely sorted and the window size is proportional to the size of the array. In all other cases where the window size is negligible, you can consider the space used to be O(1)

Conclusion

This is a very common interview question which is asked in many many interviews. There are couple of varieties of this question:

  • Find the minimum element in a sliding window of length K in a given array
  • Find K minimum elements in a sliding window of length L in a given array and so on.

I might be posting the second one in upcoming posts.

Happy Reading and Stay subscribed.