Given an array of n integer with duplicate number, and a moving window(size k), move the window at each iteration from the start of the array, find the maximum number inside the window at each moving.
For array [1, 2, 7, 7, 8], moving window size k = 3. return [7, 7, 8]
At first the window is at the start of the array like this
[|1, 2, 7| ,7, 8] , return the maximum 7;
then the window move one step forward.
[1, |2, 7 ,7|, 8], return the maximum 7;
then the window move one step forward again.
[1, 2, |7, 7, 8|], return the maximum 8;
O(n) time and O(k) memory
Solution 1. Runtime O(n * k)
Brute force solution, every time the window is moved, we can search for the max value in O(k) time.
Solution 2. Runtime O(n * log k) ?
Similarly with Sliding Window Median, use a max heap data structure;
when the size of this max heap is < k, insert the new element in O(log k);
when the size of this max heap is k, get the max value in O(log k);
when the size of this max heap is > k, remove the least recent element;
The question here is to to remove an element that is not the head/root of a heap, it takes O(k) time, not O(log k).
If the pq is already given the reference to the to-be-deleted element, then it takes O(log k) time; If not, it takes
the pq O(k) time to find the element first. We can use a tree set of self-defined Entry class. Entry contains both the element value and index information. The index is used to achieve O(k) removal operation. This is the same idea with the tree set technique used in Sliding Window Median.
Solution 3. O(n) runtime, O(k) extra space
Can we do better? The BCR is O(n) as we need to scan the input array at least once. In solution 2, we reduced the runtime
of getting the max in a window from O(k) to O(log k), assuming we can remove an arbitrary element from a pq in O(log k) time.
So, applying the BUD optimizations here, we know that finding each max value in O(log k) time is the bottleneck now.
Can we reduce it to O(1)?
The double-ended queue is the perfect data structure for this problem. It supports insertion/deletion from the front and back of the queue.
The trick is to find a way such that the largest element in the window would always appear in the front of the queue.
A natural way to think is to try to maintain the queue size the same as the window size as it is in solution 2. Try to break away from this thought and try to think outside of box. Removing redundant elements and only storing elements that need to be considered in the queue is the key to acheive an optimal O(n) solution.
Observe the following example, say, we have processed [10 5 3] and the new element is 11. Now, we could've emptied the queue without
considering elements 10, 5, 3, and insert only 11 into the queue.
From the above analysis, we drive the following alogrithm.
1. Given a new element nums[i], remove all elements that are <= nums[i] from the queue' end;
Doing this ensures the head of the deque always stores the index of the largest element of all elements currently stored in the deque. At any point, the deque stores indices whose corresponding values are in strict descending order.
2. Remove all indices from the head of the deque that is <= (i - k), if an index t is <= (i - k), it means nums[t] is out of the window already.
3. Add the index i of the new element nums[i] to the end of the deque.
4. Read the head of the deque that stores the index of current largest element's in current window.
5. Repeat until all elements are scanned.
Runtime analysis: Each index is pushed and poped at most once, so we have a runtime of O(2 * n) -- O(n)
Space: O(k)
Why do we store elements' indices instead of their actual values?
Because we need to remove the out of window elements from the head of the deque. Storing the actual value
does not give us this information. Whereas storing the indices lets you know if an index is out of window by checking
if an index is <= i - k, where i is the current index of the new element.
1 public class Solution {
2 public ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {
3 ArrayList<Integer> results = new ArrayList<Integer>();
4 if(nums == null || nums.length == 0 || nums.length < k) {
5 return results;
6 }
7 Deque<Integer> dq = new LinkedList<Integer>();
8 for(int i = 0; i < k; i++) {
9 // as long as the current element nums[i] is >= the last element at the
10 // end of the deque, remove it. nums[i] is in current window, any element
11 // that is <= is redudant and can be removed from consideration.
12 while(dq.isEmpty() == false && nums[i] >= nums[dq.peekLast()]) {
13 dq.removeLast();
14 }
15 dq.addLast(i);
16 }
17 results.add(nums[dq.peekFirst()]);
18 for(int i = k; i < nums.length; i++) {
19 while(dq.isEmpty() == false && nums[i] >= nums[dq.peekLast()]) {
20 dq.removeLast();
21 }
22 //since we insert new elements at the end of the dq, any possible
23 //elements that are out of the the current window will be on the
24 //front of the dq.
25 while(dq.isEmpty() == false && dq.peekFirst() <= i - k) {
26 dq.removeFirst();
27 }
28 dq.addLast(i);
29 results.add(nums[dq.peekFirst()]);
30 }
31 return results;
32 }
33 }
Related Problems