Sliding Window Maximum
Problem Statement
Given an array , and an integer , find the maximum element for every contiguous subarray of size .
Examples
Example 1
Input :
Output :
Explanation :
- Maximum of first window is 5.
- Maximum of second window is 9.
- Maximum of third window is 9.
- Maximum of fourth window is 9.
- Maximum of fifth window is 7.
Example 2
Input :
Output :
Explanation :
- Maximum of first window is 6.
- Maximum of second window is 7.
- Maximum of third window is 7.
- Maximum of fourth window is 7.
Constraints
Approach 1: Brute Force
The first approach that comes to our mind while reading the problem, is to run two nested loops to find the maximum element of each window of size .
The idea is quite basic, we will use two nested for loops, where the first loop will mark the starting point (say ) of the subarray of length , and the inner loop will run from to and find the maximum element in the range.
The algorithm is as follows -
- Let's say we have an array of size , we need to print the maximum of every window of size .
- Iterate from to and do the following -
- Declare a variable (say ) and initialize it very small value (say ).
- Iterate from to and do the following -
- If , update the value of to .
- Print , which now denotes the maximum element of the window of size starting from .
Note that in the outer loop we are iterating till because the starting point of the last window will be .
Pseudocode
Java Implementation
C++ Implementation
Python Implementation
Output
Complexity Analysis
- Time Complexity - The outer loops run for times while the inner loops run for times in each iteration. Hence the overall time complexity is which is equivalent to .
- Space Complexity - Since we are not using any extra space. The overall space complexity is .
Approach 2: Using Self-Balancing BST
In the last section, we used a loop to iterate for each window and find its maximum element which had cost us time on an average. Using Self-Balancing BST (AVL Tree) we can reduce this to .
As we have seen in AVL Tress, all the operations like searching, deleting, and inserting a node are time taking operations in both the average case and the worst case. If you are interested in knowing, why it is so, please go through the detailed article on AVL Trees.
The main idea is to, insert the first elements in the AVL tree and then for each to find the largest element present in the tree (which denotes the maximum element of the current window), remove elements that are no longer part of the window, and insert the element which is added to the window during iteration. Since at most nodes can be present in the tree at any instant of time, therefore all these operations will cost time on an average. And we are iterating for times, which makes the overall time complexity which is pretty efficient.
The algorithm is as follows -
- Define an AVL tree (say tree).
- Iterate through the first elements of the array, and insert them in the tree.
- Iterate from to and do the following -
- Print the maximum element of the tree.
- Delete the element at index from the tree, as it is no longer part of the window.
- Insert the element of the array in the AVL tree.
- Print the maximum element of the tree, this denotes the maximum element of the last window of size k.
Pseudocode
Note that the Code of AVL tree is very large and complicated, hence it's not worth it to discuss it here therefore we are just importing the code already written to implement it. If you are interested to learn more about AVL trees, kindly go through this.
Java Implementation
C++ Implementation
Complexity Analysis
- Time Complexity - For each ranging from 0 to , we are doing at most operations removing from AVL tree and inserting in it. Hence the time complexity is .
- Space Complexity - The maximum number of nodes present in the AVL tree can reach up to at any instant of time. Hence the space complexity is .
Approach 3: Max-Heap
In the previous approach, we have seen how we can find the sliding window maximum efficiently using AVL trees. This approach is also very similar to the previous one, here we will be using the Max-Heaps instead of AVL trees, and the rest of the logic will be the same only.
The idea is to insert all the elements which are part of the first window of size , then find the maximum among them and print it. Now before moving to the next window, remove the element that is no longer the part of any subsequent window, and add the element that will the part of the further window(s).
The algorithm is as follows -
- Define a Heap (PriorityQueue), let it be pq. Make sure that it is a max-heap and not a min-heap.
- Iterate through the first elements of the array, and insert them into the heap.
- Iterate from to and do the following -
- Print the maximum element of the heap root node.
- Remove the element at index from the heap, as it is no longer part of the window.
- Insert element of the array in the Max-Heap.
- Print the maximum element of pq, this denotes the maximum element of the last window of size k.
Pseudocode
Java Implementation
C++ Implementation
Output
Complexity Analysis
- Time Complexity - For each element we are performing logarithmic time operations (Inserting, removing from the heap). Due to this, the time complexity is .
- Space Complexity - The size of the heap can reach up to , therefore the space complexity is .
Approach 4: Deque
An important observation that we can easily make here is that, we can only consider the promising candidates of the current window. An element is considered to be promising for being a sliding window maximum if it lies in the current window and it is greatest among all the elements that lies in the window range (towards the right side).
To implement this functionality, we will introduce an interesting data structure monotonic doubly-ended queue. Don't get afraid of the name, it is just a doubly ended queue in which elements from head to tail is in decreasing order (hence it is named monotonic).
To transform a simple doubly-ended queue into a monotonic doubly ended queue, we will modify the push operation so that - "Before we push x in the queue, we pop out all elements less than x".
The algorithm is as follows -
- Create a doubly ended queue (say ) of size .
- Iterate from to and do the following -
- Pop out all elements from tail of until the inequality holds true.
- Push in .
- Now iterate from to and do the following -
- Print the element at the head of , this denotes the maximum element of the current window.
- Pop all the elements from the head of which no longer lie in the current window.
- Pop all the elements from the tail of which are smaller than or equal to .
- Push into the queue.
- Print the element at the head of the queue, this marks the maximum element of the last window.
Psuedocode
Java Implementation
C++ Implementation
Python Implementation
Output
Complexity Analysis
- Time Complexity - It can be noticed that every element of the array is pushed and popper at most once. Hence there are at max operations, and hence the time complexity is .
- Space Complexity - Since the maximum size of the queue can reach up to , the space complexity is . Also, the max value can attain is , hence we can say the upper bound is in the worst case.
Approach 5: Using Dynamic Programming
In all the approaches we have seen in the previous sections, we were processing the elements as we are sliding our window (towards the right). But if we can store some sort of information that can be used in the future to find the maximum element of the window, that will be more than good.
One good idea is - for each 0 <= i < n, store the index of next greater element to the right. Now let's see how this can help us to find the maximum element of each window of size .
We will iterate from to , and for each window starting at the index, we will find the greatest element that lies in the current window, and in case there is no greater element than the element in the range of window we will consider it to be the greatest element of the window.
The algorithm is as follows - We will split this program into two parts, In part 1 for each element, we will find the index of the next greater element toward the right, and in part 2 we will find the sliding window maximum.
Part 1 -
- Define an array (say right) of size , where right[i] will store index of the next greater element towards the right.
- Assign to right[n-1], because for the last element we consider there is an imaginary number at the position which is very large.
- Iterate from to and do the following -
- Assume the element at index is the next greater element, so store in a variable (say p).
- Now till (p lies in array bounds) and (element at index p is smaller than or equal to element at index i), update the value of p to right[p] (Index of next greater element for a[p]).
- Store the final value of p in right[i].
Part 2 -
- Initialize two variables (say i and j), where i will be used to iterate over the array and j will be used to mark the maximum element of the window.
- Iterate from to and do the following -
- If j is less than i the current maximum element is no longer in the window then assign the value of i to j.
- Iterate till right[j] lies in the current window and update value of j as j = right[j].
- If now the value of j is n, it means a[i] is the greatest element of the current window, hence print it.
- Otherwise, print a[j] that denotes the greatest element that lies in the window.
Pseudocode
Java Implementation
C++ Implementation
Python Implementation
Output
Complexity Analysis
- Time Complexity - Both part 1 and part 2 of the algorithm requires time to get executed, hence the overall time complexity is .
- Space Complexity - Since we have used the right array to store indices of the next greater element which is of size . The overall space complexity is .
Conclusion
- Sliding Window Maximum is nothing but the maximum element present in each contiguous subarray of size (given).
- They can be found in time when using the naive brute-force approach.
- However, with certain optimizations it can be brought down to by using Heaps or AVL Trees.
- Optimally it can be solved in linear time complexity either using dynamic programming or Monotonic Deque.