Question: Given
an array of numbers and a sliding window size, how to get the maximal numbers
in all sliding windows?
For example, if the input array is {2, 3, 4, 2, 6, 2, 5, 1}
and the size of sliding windows is 3, the output of maximums are {4, 4, 6, 6,
6, 5}, as illustrated in Table1.
Sliding Windows in an Array

Maximums in Sliding Windows

[2, 3, 4], 2, 6, 2, 5, 1

4

2, [3, 4, 2], 6, 2, 5, 1

4

2, 3, [4, 2, 6], 2, 5, 1

6

2, 3, 4, [2, 6, 2], 5, 1

6

2, 3, 4, 2, [6, 2, 5], 1

6

2, 3, 4, 2, 6, [2, 5, 1]

5

Table 1: Maximums of all sliding windows with size 3 in
an array {2, 3, 4, 2, 6, 2, 5, 1}. A pair of brackets indicates a sliding
window.
Analysis:
It is not difficult to get a solution with brute force: Scan numbers in every
sliding window to get its maximal value. The overall time complexity is O(nk) if the length of array is n and the size of sliding windows is k.
The naïve solution is not the best solution. Let us explore
better solutions.
Solution 1: 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.
This solution is workable. However, we may not have enough
time to write all code to implement our own queue and stack data structures
during interviews. Let us continue exploring a more concise solution.
Solution 2: 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 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. 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

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.
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;
}
Extension: 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.
The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.
The author Harry He owns all the rights of this post. If you are going
to use part of or the whole of this ariticle in your blog
or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact him via zhedahht@gmail.com . Thanks.
Is it a ACM problem:
ReplyDeletehttp://icpc.ahu.edu.cn/OJ/Problem.aspx?id=542
the solution 2 actually keeps track of every possible maximum in the sliding window. So when the window moves, it needs to decide whether or not delete the first number in the queue, and then put the new number into the queue, and compare the new number with the second newest number in that queue, if the second newest number is smaller than delete that number, and then compare with the third newest number,... So in the worst case, i think it is O(n*k) time complexity. Which is pretty bad.
ReplyDeleteconsider the following input with window size 3: <4321432143214321....>
DeleteI agree with you.
DeleteThis comment has been removed by the author.
ReplyDeletevector vec = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
ReplyDeletedeque Q;
for(int i = 0; i < vec.size(); i++) {
while (!Q.empty() && Q.back().first <= vec[i]) {
Q.pop_back();
}
Q.push_back(make_pair(vec[i], i));
while (!Q.empty() && Q.front().second + window_size <= i)
Q.pop_front();
if(Q.front().second >= window_size1) {
cout << Q.front().first << endl;
}
}
Still don't know how Mehod 1 can lead to O(1) time on finding the maximum. Even implement Queue with two Stack requires either of the two operations dequeue() or enqueue() to be O(n), while the other to be O(1), and each time you need to do both dequeue() and enqueue(). Thus, you still need O(n) to find maximum.
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteThis can be done using ksize maxheap (priority queue), where K is window size. Each step takes logn time, the complexity of this entire process is O(nlogn).
ReplyDeleteIt should be O(n.logk), no? Considering that inserting and deleting from the maxheap is O(logk)
DeleteThis comment has been removed by the author.
ReplyDeleteYour blog is good and you are sharing the right tips about UPVC Window Or Door. Thanks for great post. upvc doors  upvc doors windows
ReplyDeleteThanks for the question and discussion. However, I feel the solution you provided still takes O(n*k) time. I came up with a solution, which uses a heap and a hashmap, and gets the answer in linear time, using linear space. I am pretty confident that my solution works, and is indeed linear in time and space. Code: https://github.com/rushiagr/basicalgos/blob/master/interview/009maximuminslidingwindowofarray.cpp
ReplyDeleteThis comment has been removed by the author.
ReplyDelete