This is the second time I am hearing about this interview question, and so I should not ignore this anymore. I personally had this question in one of my interviews where I couldn't find the most optimal solution. My friend got this question in Google interview very recently and he too failed to give the best answer. So, I took my time to surf the Internet to find out the best answer.
Question:
You are given an array of size n (may be a stream also). You have a sliding window of size k. The window first boxes the first k elements of the array and slides slowly over the array by shifting its position 1 element each time. At each position of the array, you need to find the minimum element in the sliding window. i.e. you need to give the minimum of 0 to k-1 elements, then 1 to k elements, 2 to k+1 elements etc. So if your array's size is n, you have to give me n-k+1 minimum values.
E.g. Assume that the array is 5,1,3,2,6,8,4,6, and the window size is 3
You should give me 1,1,2,2,4,4. How will you give it?
Solution #1:
As you need to find out the minimum, my solution was to use a min-heap of size k and gave a solution with time complexity O(nlog(k)). My friend too thought in the same lines. First form a min heap with the first k elements (initial position of the window). Now as and when the window slides, you need to form a new min-heap by adding the next element and discard the first element. Addition of a new element is simple and will take O(log(k)) time. But for deleting an element, you need O(k) time which pushes the time higher. So instead of seeing the problem as a two step process, see it as changing the value of an element in the heap, i.e. you need to change the value of the element you want to discard to the new element that you want the heap to have. If the element that gets into the window knows which element to remove from heap (by maintaining a pointer), the problem can easily be solved in O(nlog(k)) time by simply calling min-heapify n times.
Solution #2:
However, there is a better solution for this problem in O(n) time. At any time, you will add exactly 1 new element from the stream to the window, and discard 1 element.
1. Find the minimum element in the whole list (1 in our example). Let the index of that element in the window be i (this too is 1 if the index is zero based). Insert that element in the list.
2. Now forget about the first i elements (where W[i] = min element in the whole window).
3. From i+1 to k elements, find the minimum value and add it to the list.
4. Repeat it till you add the last element of the window as an entry in the list.
In our example, among all the elements 1 is the least element. So, the result list should be 1.
Now discard the first two elements (ignore the prefix of the array such that the end element is the minimum element you have found. i.e. ignore 5 and 1). Now in the resultant array, find the minimum. i.e. 2. Add this element to the list. So the list will be 1,2.
Do the same step recursively (here only 2 elements are there, but if 2 is not the last element, you should have continued doing the same till you insert the last element in the list).
The new list that you have formed is called ascending minima.
Example:
Note: The minimum element of the window is always present as the first element of the ascending minima list.
Step 2: Adjusting ascending minima for window shift
2. As in all the cases, we took the suffix array to find the minimum element. Now there should have been cases that the newly added element is the minimum element. Search from the end of the ascending minima start discarding all elements that are > X .
3. Insert X at the end.
Now, for 1 shift of the window, you have adjusted the minima array from which you can find the minimum element of the window in O(1) time by looking at the first element.
Example:
The ascending minima of [6,2,1,5,3,4,8] is [1,3,4,8].
If the window slides and takes in the next element say 7 and discards the first element 6. How should we reconstruct the ascending minima?
1. As 6 is getting discarded right now, in case the lowest element in window was 6, it would have been the first element in the minima list, in which case should discard the first element in the minima list. Here this is not the case.
2. After shifting, the window has the following elements [2,1,5,3,4,8,7]. Our previous minima list was [1,3,4,8]. We add an element to the minima list only when that is the SMALLEST element in the sub-window. So any number > 7 say K would have entered the minima only because at that time, the sub-window had all numbers >= K. Now that 7 has come that too as the LAST element of the window, no element > 7 should be present in the minima list as the adjusted new sub-window will have 7 also from now on, and 7 is lesser than any other element in the sub-window. i.e. When we chose 8 for the minima list, the sub-window we had was only [8]. Now, as window has shifted and 7 has entered, the sub-window will be [8,7]. So, clearly 8 can't be present in the minima list. It should be 7.
3. So adjusting for a shift is the minima list becomes [1,3,4,7].
Other examples:
[1,3,3,2,5,8,7,8,9] - minima is [1,2,5,7,8,9]
Case #1: If window moves and adds 6 at the right, then:
1. 1 gets discarded from the minima list. leaving the minima as [2,5,7,8,9]
2. As 6 has entered, remove all elements from the right that are > 6 and add 6 at the end. So minima will become [2,5,6].
Case #2: If the given window moves and adds 10 instead of 6,
1. 1 gets discarded leaving the minima as [2,5,7,8,9]
2. Pop out all elements that are > 10 at the end and insert 10 at the end. So the minima will become [2,5,7,8,9,10].
Case #3: If the given window moves and adds 0
1. 1 gets discarded leaving the minima as [2,5,7,8,9]
2. Pop out all elements that are >= 0 and insert a 0 at the end. So the new minima will become [0]
Algorithm
Coming to the time complexity of the algorithm, in the worst case, all the elements might enter the minima array and all of them might get discarded from the array both of which are O(n). So the whole algorithm works in O(n) time.
Question:
You are given an array of size n (may be a stream also). You have a sliding window of size k. The window first boxes the first k elements of the array and slides slowly over the array by shifting its position 1 element each time. At each position of the array, you need to find the minimum element in the sliding window. i.e. you need to give the minimum of 0 to k-1 elements, then 1 to k elements, 2 to k+1 elements etc. So if your array's size is n, you have to give me n-k+1 minimum values.
E.g. Assume that the array is 5,1,3,2,6,8,4,6, and the window size is 3
You should give me 1,1,2,2,4,4. How will you give it?
Solution #1:
As you need to find out the minimum, my solution was to use a min-heap of size k and gave a solution with time complexity O(nlog(k)). My friend too thought in the same lines. First form a min heap with the first k elements (initial position of the window). Now as and when the window slides, you need to form a new min-heap by adding the next element and discard the first element. Addition of a new element is simple and will take O(log(k)) time. But for deleting an element, you need O(k) time which pushes the time higher. So instead of seeing the problem as a two step process, see it as changing the value of an element in the heap, i.e. you need to change the value of the element you want to discard to the new element that you want the heap to have. If the element that gets into the window knows which element to remove from heap (by maintaining a pointer), the problem can easily be solved in O(nlog(k)) time by simply calling min-heapify n times.
Solution #2:
However, there is a better solution for this problem in O(n) time. At any time, you will add exactly 1 new element from the stream to the window, and discard 1 element.
Step 1: Finding ascending minima:
Assume that the current window is 5,1,3,2. You need to form a list with the following algorithm -1. Find the minimum element in the whole list (1 in our example). Let the index of that element in the window be i (this too is 1 if the index is zero based). Insert that element in the list.
2. Now forget about the first i elements (where W[i] = min element in the whole window).
3. From i+1 to k elements, find the minimum value and add it to the list.
4. Repeat it till you add the last element of the window as an entry in the list.
In our example, among all the elements 1 is the least element. So, the result list should be 1.
Now discard the first two elements (ignore the prefix of the array such that the end element is the minimum element you have found. i.e. ignore 5 and 1). Now in the resultant array, find the minimum. i.e. 2. Add this element to the list. So the list will be 1,2.
Do the same step recursively (here only 2 elements are there, but if 2 is not the last element, you should have continued doing the same till you insert the last element in the list).
The new list that you have formed is called ascending minima.
Example:
Assume that the window is [6,2,1,5,3,4,8].
1. Start with an empty ascending minima array, call it ama = {}
2. In the window, find the minimum element in the window (1 at the 3rd position). Add that minimum element to the ama list, and ignore all elements till 1 in the window,
So ama = {1} and sub-window to be processed = {5,3,4,8}.
3. Find the smallest element in the sub-window to be processed (3 at the 2nd position in the sub-window). Add 3 to the ama list and discard all elements till 3 in the sub-window.
So, ama = {1,3} and sub-window to be processed = {4,8}.
4. Find the smallest element again in the sub-window (4 at the 1st position), and add it to the ama list. Ignore elements till 4.
So, ama = {1,3,4} and sub-window to be processed = {8}.
5. Find the smallest element in the window again. i.e. (8 at the 1st position). Add it to the ama list. Now discard all elements till 8 which results the sub-window as an empty array.
ama={1,3,4,8} and sub-window to be processed = {}
6. End the process as sub-window to be processed is empty.
Other examples:
[8,9,5,3,6,5,1,1,0] - ascending minima = [0]
[7,4,8,6,3,4,2,1,2] - ascending minima = [1,2]
[1,2,3,4,5,6,7,8,9] - ascending minima = [1,2,3,4,5,6,7,8,9]
[9,8,7,6,5,4,3,2,1] - ascending minima = [1]
[9,1,1,3,4,2,6,8,9] - ascending minima = [1,2,6,8,9] (In case duplicates are there, take the last one).
Algorithm:
def ascending_minima(arr, minima = [])return minima if arr.empty?return minima << arr[0] if arr.size == 1min_index = 01..(arr.size-1).each { |i| min_index = i if arr[i] < arr[min_index]}minima << arr[min_index]minima = ascending_minima(arr[min_index+1..arr.size-1], minima)return minimaend
Note: The minimum element of the window is always present as the first element of the ascending minima list.
Step 2: Adjusting ascending minima for window shift
What happens when a window shifts by an element? The first element in the previous window gets discarded and a new element gets added at the end of the window. As, from ascending minima, you can easily find the smallest element of a window (by peeking into the first element of the ascending minima). Let us try how to get the ascending minima without reconstructing it from scratch by using the previous ascending minima itself.
1. If the element that you discard is the first element in the ascending minima, you need to get rid of that element from the ascending minima.2. As in all the cases, we took the suffix array to find the minimum element. Now there should have been cases that the newly added element is the minimum element. Search from the end of the ascending minima start discarding all elements that are > X .
3. Insert X at the end.
Now, for 1 shift of the window, you have adjusted the minima array from which you can find the minimum element of the window in O(1) time by looking at the first element.
Example:
The ascending minima of [6,2,1,5,3,4,8] is [1,3,4,8].
If the window slides and takes in the next element say 7 and discards the first element 6. How should we reconstruct the ascending minima?
1. As 6 is getting discarded right now, in case the lowest element in window was 6, it would have been the first element in the minima list, in which case should discard the first element in the minima list. Here this is not the case.
2. After shifting, the window has the following elements [2,1,5,3,4,8,7]. Our previous minima list was [1,3,4,8]. We add an element to the minima list only when that is the SMALLEST element in the sub-window. So any number > 7 say K would have entered the minima only because at that time, the sub-window had all numbers >= K. Now that 7 has come that too as the LAST element of the window, no element > 7 should be present in the minima list as the adjusted new sub-window will have 7 also from now on, and 7 is lesser than any other element in the sub-window. i.e. When we chose 8 for the minima list, the sub-window we had was only [8]. Now, as window has shifted and 7 has entered, the sub-window will be [8,7]. So, clearly 8 can't be present in the minima list. It should be 7.
3. So adjusting for a shift is the minima list becomes [1,3,4,7].
Other examples:
[1,3,3,2,5,8,7,8,9] - minima is [1,2,5,7,8,9]
Case #1: If window moves and adds 6 at the right, then:
1. 1 gets discarded from the minima list. leaving the minima as [2,5,7,8,9]
2. As 6 has entered, remove all elements from the right that are > 6 and add 6 at the end. So minima will become [2,5,6].
Case #2: If the given window moves and adds 10 instead of 6,
1. 1 gets discarded leaving the minima as [2,5,7,8,9]
2. Pop out all elements that are > 10 at the end and insert 10 at the end. So the minima will become [2,5,7,8,9,10].
Case #3: If the given window moves and adds 0
1. 1 gets discarded leaving the minima as [2,5,7,8,9]
2. Pop out all elements that are >= 0 and insert a 0 at the end. So the new minima will become [0]
Algorithm
def get_minima_adjusted_to_shift(previous_window, new_element, previous_minima) previous_minima.delete(0) if previous_window[0] == previous_minima[0] while (previous_minima.last > new_element) previous_minima.delete(previous_minima.size-1) end previous_minima << new_element return previous_minima end
Coming to the time complexity of the algorithm, in the worst case, all the elements might enter the minima array and all of them might get discarded from the array both of which are O(n). So the whole algorithm works in O(n) time.
It would be helpful if u could show with a step by step example for the soln 2
ReplyDeleteAnusuya, I have added few examples in the post to explain the solution better.
ReplyDelete