Problem Statement
Question: A long array A[] is given to you. There is a sliding window of size w, which is moving from the very left of the array to the very right. You can only see the w numbers in the window. Each time the sliding window moves rightwards by one position.
Example:
The array is [1 3 -1 -3 5 3 6 7], and w is 3.
Input: A long array A[], and a window width w
Output: An array B[], B[i] is the maximum value of from A[i] to A[i+w-1]
Example 2
arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}
w= 3
Output :
3 3 4 5 5 5 6
Code(Java):
Time complexity - O(n)
Can we do better?
Of-course we can do better. The word max value rings the bell in our head - we can use priority queue?
A heap data structure quickly comes to mind. We could boost the run time to approximately O(n lg w) (Note that I said approximately because the size of the heap changes constantly and averages about w). Insert operation takes O(lg w) time, where w is the size of the heap. However, getting the maximum value is cheap, it merely takes constant time as the maximum value is always kept in the root (head) of the heap.
As the window slides to the right, some elements in the heap might not be valid anymore (range is outside of the current window). How should you remove them? You would need to be somewhat careful here. Since you only remove elements that are out of the window’s range, you would need to keep track of the elements’ indices too. Finding the element to delete in the heap, will take O(w) and O(lgW) time for heapify operation. So, time complexity for n elements, will be again O(n*(w+lgw)) = O(nw), which is same as brute force.
But there are couple of solutions. Lets discuss them one by one. Can we use similar structure to heap, like priority queue?
Here are the steps:
Let us take the array {2, 3, 4, 2, 6, 2, 5, 1} as an example and window size as 3 to analyze the solution step by step.
It is noticeable that the number at the front is beyond the scope the current sliding window, and it should be popped off. How do we know whether the number at the front of the queue is out of sliding window? Rather than storing numbers in the queue directly, we can store indices instead. If the distance between the index at the front of queue and the index of the current number to be pushed is greater than or equal to the window size, the number corresponding to be the index at the font of queue is out of sliding window.
The analysis process above is summarized in Table 2.
Table 2: The process to get the maximal number in all
sliding windows with window size 3 in the array {2, 3, 4, 2, 6, 2, 5, 1}. In
the column “Indices in queue”, the number inside a pair of parentheses is the
number indexed by the number before it in the array.
Code (c++)
We can implement a solution based on the analysis above. Some sample code in C++ is shown below, which utilizes the type deque of STL.
The following is the sample code:
Since this solution is similar to the second solution to get maximums of sliding windows, we won’t analyze the process step by step, and leave it as an exercise if you are interested.
Time Complexity of step 1 is O(w lg(w)).
Time Complexity of steps 2(a), 2(b) and 2(c) is O(Logk). Since steps 2(a), 2(b) and 2(c) are in a loop that runs n-k+1 times, time complexity of the complete algorithm is O(wLogw + (n-k+1)*Logw) which can also be written as O(nLogw).
We create a Dequeue, Qi of capacity w, that stores only useful elements of current window of w elements. An element is useful if it is in current window and is greater than all other elements on left side of it in current window. We process all array elements one by one and maintain Qi to contain useful elements of current window and these useful elements are maintained in sorted order. The element at front of the Qi is the largest and element at rear of Qi is the smallest of current window.
Code(java)
Please suggest, if you have some other methods.
Source
Question: A long array A[] is given to you. There is a sliding window of size w, which is moving from the very left of the array to the very right. You can only see the w numbers in the window. Each time the sliding window moves rightwards by one position.
Example:
The array is [1 3 -1 -3 5 3 6 7], and w is 3.
Window position Max --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7
Input: A long array A[], and a window width w
Output: An array B[], B[i] is the maximum value of from A[i] to A[i+w-1]
Example 2
arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}
w= 3
Output :
3 3 4 5 5 5 6
Solution
Method 1: Brute force
The obvious solution with run time complexity of O(nw) is definitely not efficient enough. Every time the window is moved, we have to search for the maximum from w elements in the window.Code(Java):
void windowMaxBrute(int arr[], int w)
{
int j, max;
int n = arr.length;
int b[] = new int[arr.length];
int k=0;//tracker for array b
for (int i = 0; i <= n-w; i++)
{
max = arr[i];
for (j = 1; j < w; j++)
{
if (arr[i+j] > max)
max = arr[i+j];
}
b[k] = max;
}
}
Time complexity - O(n)
Can we do better?
Method 2z : Using Heap (will not work)
Of-course we can do better. The word max value rings the bell in our head - we can use priority queue?
A heap data structure quickly comes to mind. We could boost the run time to approximately O(n lg w) (Note that I said approximately because the size of the heap changes constantly and averages about w). Insert operation takes O(lg w) time, where w is the size of the heap. However, getting the maximum value is cheap, it merely takes constant time as the maximum value is always kept in the root (head) of the heap.
As the window slides to the right, some elements in the heap might not be valid anymore (range is outside of the current window). How should you remove them? You would need to be somewhat careful here. Since you only remove elements that are out of the window’s range, you would need to keep track of the elements’ indices too. Finding the element to delete in the heap, will take O(w) and O(lgW) time for heapify operation. So, time complexity for n elements, will be again O(n*(w+lgw)) = O(nw), which is same as brute force.
But there are couple of solutions. Lets discuss them one by one. Can we use similar structure to heap, like priority queue?
Method 2a - Maximal value in a queue
A window can be viewed as a queue. When it slides, a number is pushed into its back, and its front is popped off. Therefore, the problem is solved if we can get the maximal value of a queue. There are no straightforward approaches to getting the maximal value of a queue. However, there are solutions to get the maximal value of a stack, which is similar to the solution introduced in the blog “Stack with Function min()”. Additionally, a queue can also be implemented with two stacks (details are discussed in another blog “Queue implemented with Two Stacks”). If a new type of queue is implemented with two stacks, in which a function max() is defined to get the maximal value, the maximal value in a queue is the greater number of the two maximal numbers in two stacks. Lets call this queue QMax.Here are the steps:
- Enqueue w elements into the QMax. Time complexity = O(w)
- Get the max element from the QMax, and print it, which takes constant time. O(1)
- Dequeue element from QMax. O(1)
- Enqueue next element in QMax, O(1)
- Repeat step 2, 3, 4 until we reach end of array.
Method 2b - Saving the maximal value into the front of a queue
Instead of pushing every numbers inside a sliding window into a queue, we try to push the candidates of maximum only into a queue.Let us take the array {2, 3, 4, 2, 6, 2, 5, 1} as an example and window size as 3 to analyze the solution step by step.
- The first number in the array is 2, we push it into a queue.
- The second number is 3, which is greater than the previous number 2. The number 2 should be popped off, because it is less than 3 and it has no chance to be the maximal value. There is only one number left in the queue when we pop 2 at the back and push 3 at the back.
- The operations are similar when we push the next number 4. There is only a number 4 remaining in the queue. Now the sliding window already has three elements, we can get the maximum value at the front of the queue.
- We continue to push the fourth number i.e. 2. It is pushed at the back of queue, because it is less than the previous number 4 and it might be a maximal number in the future when the previous numbers are popped off. There are two numbers, 4 and 2, in the queue, and 4 is the maximum.
- The next number to be pushed is 6. Since it is greater than the existing numbers, 4 and 2, these two numbers can be popped off because they have no chance to be the maximum. Now there is only one number in the queue, which is 6, after the current number is pushed. Of course, the maximum is 6.
- The next number is 2, which is pushed into the back of the queue because it is less than the previous number 6. There are two numbers in the queue, 6 and 2, and the number 6 at the front of the queue is the maximal value.
- It is time to push the number 5. Because it is greater than the number 2 at the back of the queue, 2 is popped off and then 5 is pushed. There are two numbers in the queue, 6 and 5, and the number 6 at the front of the queue is the maximal value. Now let us push the last number 1. It can be pushed into the queue.
It is noticeable that the number at the front is beyond the scope the current sliding window, and it should be popped off. How do we know whether the number at the front of the queue is out of sliding window? Rather than storing numbers in the queue directly, we can store indices instead. If the distance between the index at the front of queue and the index of the current number to be pushed is greater than or equal to the window size, the number corresponding to be the index at the font of queue is out of sliding window.
The analysis process above is summarized in Table 2.
| Step | Number to Be Pushed | Numbers in Sliding Window | Indices in queue | Maximum in Window |
| 1 | 2 | 2 | 0(2) | |
| 2 | 3 | 2, 3 | 1(3) | |
| 3 | 4 | 2, 3, 4 | 2(4) | 4 |
| 4 | 2 | 3, 4, 2 | 2(4), 3(2) | 4 |
| 5 | 6 | 4, 2, 6 | 4(6) | 6 |
| 6 | 2 | 2, 6, 2 | 4(6), 5(2) | 6 |
| 7 | 5 | 6, 2, 5 | 4(6), 6(5) | 6 |
| 8 | 1 | 2, 5, 1 | 6(5), 7(1) | 5 |
Code (c++)
We can implement a solution based on the analysis above. Some sample code in C++ is shown below, which utilizes the type deque of STL.
vector<int> maxInWindows(const vector<int>& numbers, int windowSize)
{
vector<int> maxInSlidingWindows;
if(numbers.size() >= windowSize && windowSize > 1)
{
deque<int> indices;
for(int i = 0; i < windowSize; ++i)
{
while(!indices.empty() && numbers[i] >= numbers[indices.back()])
indices.pop_back();
indices.push_back(i);
}
for(int i = windowSize; i < numbers.size(); ++i)
{
maxInSlidingWindows.push_back(numbers[indices.front()]);
while(!indices.empty() && numbers[i] >= numbers[indices.back()])
indices.pop_back();
if(!indices.empty() && indices.front() <= i - windowSize)
indices.pop_front();
indices.push_back(i);
}
maxInSlidingWindows.push_back(numbers[indices.front()]);
}
return maxInSlidingWindows;
}
Method 2c - Another solution to get the maximum of a queue
As we mentioned before, a sliding window can be viewed as a queue. Therefore, we can implement a new solution to get the maximal value of a queue based on the second solution to get the maximums of sliding windows.The following is the sample code:
template<typename T> class QueueWithMax
{
public:
QueueWithMax(): currentIndex(0)
{
}
void push_back(T number)
{
while(!maximums.empty() && number >= maximums.back().number)
maximums.pop_back();
InternalData internalData = {number, currentIndex};
data.push_back(internalData);
maximums.push_back(internalData);
++currentIndex;
}
void pop_front()
{
if(maximums.empty())
throw new exception("queue is empty");
if(maximums.front().index == data.front().index)
maximums.pop_front();
data.pop_front();
}
T max() const
{
if(maximums.empty())
throw new exception("queue is empty");
return maximums.front().number;
}
private:
struct InternalData
{
T number;
int index;
};
deque<InternalData> data;
deque<InternalData> maximums;
int currentIndex;
};
Since this solution is similar to the second solution to get maximums of sliding windows, we won’t analyze the process step by step, and leave it as an exercise if you are interested.
Method 3 - Use Self-Balancing BST
This is similar to 2z.
- Pick first k elements and create a Self-Balancing Binary Search Tree (BST) of size w.
- Run a loop for i = 0 to n – w
- Get the maximum element from the BST, and print it.
- Search for arr[i] in the BST and delete it from the BST.
- Insert arr[i+w] into the BST.
This solution is similar to 2z(using heap), but note that delete is less costly operation, as instead of O(w), we will be taking O(lg w).
Time Complexity:Time Complexity of step 1 is O(w lg(w)).
Time Complexity of steps 2(a), 2(b) and 2(c) is O(Logk). Since steps 2(a), 2(b) and 2(c) are in a loop that runs n-k+1 times, time complexity of the complete algorithm is O(wLogw + (n-k+1)*Logw) which can also be written as O(nLogw).
Method 4 - Usint Dequeue
This method is similar to method 2b.We create a Dequeue, Qi of capacity w, that stores only useful elements of current window of w elements. An element is useful if it is in current window and is greater than all other elements on left side of it in current window. We process all array elements one by one and maintain Qi to contain useful elements of current window and these useful elements are maintained in sorted order. The element at front of the Qi is the largest and element at rear of Qi is the smallest of current window.
Code(java)
void windowMaxDeque(int arr[], int w)
{
// Create a Double Ended Queue, Qi that will store indexes of array elements
// The queue will store indexes of useful elements in every window and it will
// maintain decreasing order of values from front to rear in Qi, i.e.,
// arr[Qi.front[]] to arr[Qi.rear()] are sorted in decreasing order
Deque <Integer > Qi = new Deque < >(w);
int n = arr.length;
// Process first w (or first window) elements of array
int i;
for (i = 0; i < w; ++i)
{
// For very element, the previous smaller elements are useless so
// remove them from Qi
while ( (!Qi.empty()) && arr[i] >= arr[Qi.back()])
Qi.pop_back(); // Remove from rear
// Add new element at rear of queue
Qi.push_back(i);
}
// Process rest of the elements, i.e., from arr[w] to arr[n-1]
for ( ; i < n; ++i)
{
// The element at the front of the queue is the largest element of
// previous window, so print it
cout < < arr[Qi.front()] < < " ";
// Remove the elements which are out of this window
while ( (!Qi.empty()) && Qi.front() <= i - w)
Qi.pop_front(); // Remove from front of queue
// Remove all elements smaller than the currently
// being added element (remove useless elements)
while ( (!Qi.empty()) && arr[i] >= arr[Qi.back()])
Qi.pop_back();
// Add current element at the rear of Qi
Qi.push_back(i);
}
// Print the maximum element of last window
System.out.println(arr[Qi.front()]);
}
// Driver program to test above functions
public static void main(String[] args)
{
int arr[] = {12, 1, 78, 90, 57, 89, 56};
int w = 3;
windowMaxDeque(arr, w);
}
Please suggest, if you have some other methods.
Source
0 comments:
Post a Comment