## Thursday, February 16, 2012

### No. 33 - Maximums in Sliding Windows

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.

1. Is it a ACM problem:
http://icpc.ahu.edu.cn/OJ/Problem.aspx?id=542

1. Very much useful article. Kindly keep blogging

Java Training in Chennai

Java Online Training India

2. 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.

1. consider the following input with window size 3: <4321432143214321....>

2. I agree with you.

3. This comment has been removed by the author.

4. vector vec = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
deque 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_size-1) {
cout << Q.front().first << endl;
}
}

5. 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.

6. This comment has been removed by the author.

7. This can be done using k-size max-heap (priority queue), where K is window size. Each step takes logn time, the complexity of this entire process is O(nlogn).

1. It should be O(n.logk), no? Considering that inserting and deleting from the max-heap is O(logk)

8. This comment has been removed by the author.

9. Your blog is good and you are sharing the right tips about UPVC Window Or Door. Thanks for great post. upvc doors | upvc doors windows

10. Thanks 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/basic-algos/blob/master/interview/009-maximum-in-sliding-window-of-array.cpp

11. This comment has been removed by the author.

12. Thanks for your post which is truly informative for us and we will surely keep visiting this website.
Sliding Window Replacement
Windows And Doors Phoenix

Θωρακισμένες πόρτες

14. Hi There,

Hot! That was HOT! Glued to the Maximums in Sliding Windows your proficiency and style!

We have a customer in Denmark whose legal department is asking for the physical address of the data center in which their data is being processed. The region/AZ in question would be eu-west-1a+b.
Is there any chance AWS will disclose the address for this purpose?

I read multiple articles and watched many videos about how to use this tool - and was still confused! Your instructions were easy to understand and made the process simple.

Thanks,

15. Salaam,

Interesting piece!Great to see someone write No. 33 - Maximums in Sliding Windows who is not a fanatic or a complete skeptic.

I started using EC2 again one month back and today I realized I did't have any payment methods registered. Turns out last month's bill was charged to my old payment method, which was already deleted. I think this is a very unreasonable thing to do. So is this normal behavior? If the answer is no, how do I make sure the deleted method won't be charged again? If the answer is yes, I have to following feedbacks: AWS Training USA

Thanks a lot. This was a perfect step-by-step guide. Don’t think it could have been done better.

Cheers,
Ajeeth

16. Thanks for posting the useful information to my vision. This is excellent information,.

17. Hi, Its a great Post. Thanks For Sharing Me a Beautiful Information.
CASEMENT WINDOWS

18. Select for superb eurowindows from wood? Goto to that resource!

19. Great info! Thanks for distribution. The current stories about double-glazed windows. See at that location. Architecture news on this site

20. Good day. Nice story! Absolutely attractive. I recommend nail service diamondbeauty.ru. Good luck for you.

21. Добрый вечер! Посмотрите путеводитель инновационных медицинских препаратов. В справочное издание включены данные о почти 700 используемых медикаментозных средствах, выпускаемых отечественными и зарубежными фармфирмами. О каждом лекарстве имеется полнейшая информация: состав и форма выпуска, целительные характеристики, показания к использованию, правила использования, противопоказания, вероятные побочные эффекты, взаимодействие с алкогольными напитками и взаимодействие иными лекарственными препаратами, кроме того способность употребления при грудном вскармливании, беременности. В путеводитель включен тематический указатель, в каком представлена информация о том, какое медикаментозное средство нужно использовать при каких-то болезнях, состояниях, синдромах. Справочник можно прочитать на специализированном https://www.all-medications.ru/. Не откладывайте визит к специалисту! Пенициллиназа, Каптоприл, Трихлорэтилен, Парацетамол / фенилэфрин / кофеин / терпингидрат / аскорбиновая кислота, Колхицин, Ропивакаин,

22. Параллельно-раздвижные двери и окна – PSK-портал выбираются специально для сохранения незаполненного, свободного пространства. Обычные варианты окон и дверей открываются вовнутрь дома, что занимает достаточно значительную область места в помещении. Современные модели дают возможность избежать этой трудности, увеличить воздушный и световой поток в здании.
Подъемно-сдвижной портал являются системами, что обладают весьма широкой площадью стекла. Ради обеспечения возможности открытия створок присутствуют нижние и верхние полозья, с помощью которых створка легко и бесшумно движется.
Скольжение осуществляется при помощи ходовых роликов, которые имеют в своем составе опору в качестве компонентов армирования, позволяющим максимально равномерно распределять вес по по всей двери. Они позволяют стеклопакету передвигаться во всевозможных режимах (сдвига, наклона).
Высота створки двери или окна должна быть не более 2360 мм, а ширина окна имеет возможность изменяться от 670 мм до 160 см. В зависимости от суммарного веса (может составлять от 100 кг до 200 кг), на параллельно-раздвижную дверь монтируется определенная фурнитура для обеспечения надежного функционирования створок, роста срока функционирования. Ширина свободного проема может достигать 2000 мм.
Подъемно-сдвижные порталы могут похвастаться замечательными герметичными свойствами, хорошими показателями звуко-, термоизоляции, имеют высокий уровень противовзломности, прекрасно подойдут для всех вариантов нынешних профилей. При установке используют опоясывающие щеточные уплотнители, что ощутимо улучшают работу створок.
В том случае, если вам хочется оформить большой загородный дом, городскую квартиру, лоджию или балкон согласно модным тенденциям в дизайне, то фирма-изготовитель СВ Окна изготовит и сделает монтаж параллельно-раздвижных окон и дверей.

23. Немногие компании-производители косметических препаратов могли бы похвастаться тем, что их товар попал в число победителей, предпочитаемых членами королевских домов. Компания-производитель Lebel Cosmetics уже более 30 лет поставляет свою продукцию в японский императорский дом. Неудивительно, что, заслужив титул косметики №1 в Японии, средства для фитоламинирования волос Лебел в салоне легко захватила рынок Европы и уже покорила сердца большого количества девушек США и Канады.

24. Are you looking for UPVC doors and windows in Delhi Then Visit Spectrum upvc for mor information

25. Thank you for sharing this.
Manufacturing High Quality Residential & Commercial Doors and Windows, well recognized & reputed by homeowners, renovators, architects and builders. Proudly Australian owned & operated for over 60 years.
Aluminium and glazing