Solve sliding window maximum problem

In this post we are gonna discuss approaches to solve sliding window maximum

Problem Statement :

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

Example:

Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3

Output: [3,3,5,5,6,7]

Step by step solution to the problem :

There are various ways we can solve this problem, easiest way would be keeping one max heap (https://en.wikipedia.org/wiki/Heap_(data_structure)) of window size k. Whenever we iterate through the array, we delete the element going out of current window, add current element to the heap and call heapify. The result will be the top element of the heap. But this is not an efficient approach as in worst case heapify will take O(logk) time and you have to call heapify for n times.So overall time complexity will be O(nlogk).

We will discuss two efficient approach to solve this problem :

1. We will use double ended queue to solve it and will use a trick to ensure that the front of the queue will always have the largest element in the window. The trick is :

We know the queue will at max contain k elements. Now if we get an element lets say e at ith index of the array, we will keep on deleting the elements who are less than ith index’s element from the back of the queue as those element can’t be maximum in current window as well as subsequent next windows.

while(!deque.isEmpty() && nums[deque.peekLast()]<nums[i]) deque.pollLast();

this line is doing the trick. This algorithm runs at O(n).

2. This solution is quite intuitive if we observe the array carefully window by window

For an index i, let’ s say the max number in the left side of the window till (i+k)th element is lMax, and max number starting from ith element till the end of the window is rMax. lMax covers all left side elements from end of the window and rMax covers all right side elements from start of the window. So we can easily conclude the result array[i]=Maximum of( lMax, rMax).

I know it’s confusing. Let’s explain more in details by going through one example

A = [2,1,3,4,6,3,8,9,10,12,56], w=4
partition the array in blocks of size w=4. The last block may have less then w.
2, 1, 3, 4 | 6, 3, 8, 9 | 10, 12, 56|
Traverse the list from start to end and calculate max_so_far. Reset max after each block boundary (of w elements).
left_max[] = 2, 2, 3, 4 | 6, 6, 8, 9 | 10, 12, 56
Similarly calculate max in future by traversing from end to start.
right_max[] = 4, 4, 4, 4 | 9, 9, 9, 9 | 56, 56, 56
now, sliding max at each position i in current window, sliding-max(i) = max{right_max(i), left_max(i+w-1)}
sliding_max = 4, 6, 6, 8, 9, 10, 12, 56

The complete code for this problem can be found in https://github.com/GyanTech877/algorithms/blob/master/slidingwindow/SlidingWindowMaximum.java

Happy Learning 😎