Given an array of n integers & a window of size w, keep sliding the window from the left-most to the right-most while emitting the maximum of the current window before every move.
The brute-force solution will work in O(nw) because for each of the (n-w) possible moves of the window, we need to look at all the w elements in each of those windows.
A slight improvement is possible by using a heap data structure. Maintain a max-heap of the pair (element & position). While removing an element and finding the replacement for the root, keep removing the elements that are not required. In the worst case, there would a space requirement of O(n) to achieve this.
The best approach for this problem is to use a double-ended queue (deque) data structure. The idea is to keep just the minimal number of elements in this queue while doing the operations. For example, when the current queue has (3 1 5) and the incoming element is 7, then there's no need to keep any of the elements in the queue other than the incoming one. So, keep inserting the elements into the back of the queue as long as they are smaller than the current last. Also, if you store the positions instead of the actual numbers in the deque, it would be easy to eliminate the stale ones from the front. This can run in O(n) as the numbers are inserted/deleted constant number of times.
The brute-force solution will work in O(nw) because for each of the (n-w) possible moves of the window, we need to look at all the w elements in each of those windows.
A slight improvement is possible by using a heap data structure. Maintain a max-heap of the pair (element & position). While removing an element and finding the replacement for the root, keep removing the elements that are not required. In the worst case, there would a space requirement of O(n) to achieve this.
The best approach for this problem is to use a double-ended queue (deque) data structure. The idea is to keep just the minimal number of elements in this queue while doing the operations. For example, when the current queue has (3 1 5) and the incoming element is 7, then there's no need to keep any of the elements in the queue other than the incoming one. So, keep inserting the elements into the back of the queue as long as they are smaller than the current last. Also, if you store the positions instead of the actual numbers in the deque, it would be easy to eliminate the stale ones from the front. This can run in O(n) as the numbers are inserted/deleted constant number of times.
No comments:
Post a Comment