# Sliding window min/max, priority queue & Monotonic Queue

--

Given 1 D array, how to find the min/max value in a sliding window? We have three ways:

• O(n²) naive way. two for loops
• O(n log n) using priority queue + soft deletion
• O(n) monotonic queue.

The naive way and priority queue solutions are relatively easy to be understood. Here I’d like to focus on understanding the monotonic queue solution.

# Monotonic queue

what is the maximum value so far in the list {3, 4, 5, 1, 8, 10}

`#include<bits/stdc++.h>using namespace std;int main(){vector<int> a={3, 4, 5, 1, 8, 10};int max_val_sofar = INT_MIN;for (auto &item: a){max_val_sofar = max(max_val_sofar, item);cout<<max_val_sofar<<endl;}}Output is3455810`

The solution above is pretty nature and pretty straightforward.

## using priority queue

`#include<bits/stdc++.h>using namespace std;int main(){vector<int> a={3, 4, 5, 1, 8, 10};priority_queue<int> pq;int max_val_sofar = INT_MIN;for (auto &item: a){    pq.push(item);    max_val_sofar = pq.top();    cout<<max_val_sofar<<endl;}}`

Yes, we successfully change the complexity from O(n) to O(n log n) by using a priority queue.

## using monotonic queue

`#include<bits/stdc++.h>using namespace std;int main(){vector<int> a={3, 4, 5, 1, 8, 10};deque<int> dq;int max_val_sofar = INT_MIN;for (auto &item: a){    cout<<"dq"<<endl;    for(auto &d:dq)cout<<d<<endl;    while(!dq.empty() and item>=dq.back()) {dq.pop_back();}    if(dq.empty()) dq.push_back(item);    max_val_sofar = dq.back();    cout<<"max val sofar"<<max_val_sofar<<endl;}}output:dqmax val sofar3dq3max val sofar4dq4max val sofar5dq5max val sofar5dq5max val sofar8dq8max val sofar10`

We can see by using similar logic as the monotonic queue, we can get the same results with the complexity of O(n) and space complexity is also O(n). Since each time, only one element is put in the deque, we don’t need a deque, we just use an integer variable that will be fine. This explains why we don’t use a deque to solve this problem.

After we get familiar to the monotonic queue solution from a simple example, let’s do something real.

## A real problem can be solved by using a monotonic queue

what is the maximum sliding window value so far in the list {3, 4, 5, 1, 8, 10}, the window size should be less or equal to 3?

Now, we can see a slight difference between this one and the above example which does not have any constraints.

## increasing monotonic queue

`/** * Using an increasing deque to solve this problem *  * **/#include<bits/stdc++.h>using namespace std;int main(){    const int K = 3;vector<int> a={3, 4, 5, 1, 8, 10};deque<pair<int, int>> increasing_dq;int max_val_sofar = INT_MIN;int i=0;for(;i<a.size();++i){    cout<<"i"<<i<<endl;    while(!increasing_dq.empty() &&        (a[i]>=increasing_dq.back().first ||i-increasing_dq.back().second>K-1)) {            increasing_dq.pop_back();}    if (increasing_dq.empty()){        increasing_dq.emplace_back(a[i], i);        max_val_sofar = max(max_val_sofar, a[i]);    }    else{        max_val_sofar =  max(max_val_sofar, increasing_dq.back().first);        // if the queue is not empty and the front element is invalid or         // the front element is valid however it has a smaller or equal value to the current online        while (!increasing_dq.empty() &&         (i-increasing_dq.front().second>K-1 ||increasing_dq.front().first<=a[i])){        increasing_dq.pop_front();}        increasing_dq.emplace_front(a[i], i);    }    cout<<"max val sofar"<<max_val_sofar<<endl;}return 0;}Output:i0max val sofar3i1max val sofar4i2max val sofar5i3max val sofar5i4max val sofar8i5max val sofar10`

## Decreasing monotonic queue

`/** * Using an decreasing deque to solve this problem *  * **/#include<bits/stdc++.h>using namespace std;int main(){    const int K = 3;vector<int> a={3, 4, 5, 1, 8, 10};deque<pair<int, int>> decreasing_dq;int max_val_sofar = INT_MIN;int i=0;for(;i<a.size();++i){    cout<<"i"<<i<<endl;    while(!decreasing_dq.empty() &&        (i-decreasing_dq.front().second>K-1 || a[i]>=decreasing_dq.front().first )) {            decreasing_dq.pop_front();}    if (decreasing_dq.empty()){        decreasing_dq.emplace_front(a[i], i);        max_val_sofar = max(max_val_sofar, a[i]);    }    else{        max_val_sofar =  max(max_val_sofar, decreasing_dq.front().first);        // if the queue is not empty and the front element is invalid or         // the front element is valid however it has a smaller or equal value to the current online        while (!decreasing_dq.empty() &&         (i-decreasing_dq.back().second>K-1 ||decreasing_dq.back().first<=a[i])){        decreasing_dq.pop_back();}        decreasing_dq.emplace_back(a[i], i);    }    cout<<"max val sofar"<<max_val_sofar<<endl;}return 0;}outputi0max val sofar3i1max val sofar4i2max val sofar5i3max val sofar5i4max val sofar8i5max val sofar10`

## 239. Sliding Window Maximum

Video explanation in Chinese can be found in [3]

Naive O(n²) solution got TLE

`/*17 / 18 test cases passed.Status: Time Limit Exceeded*/class Solution {public:    vector<int> maxSlidingWindow(vector<int>& nums, int k) {        vector<int> ret;        const int n = nums.size();        for (int i = k-1; i < n; ++i)        {            ret.push_back(*max_element(nums.begin() + i - k + 1,                                       nums.begin() + i + 1));        }        return ret;    }};`

Priority queue + soft deletion get AC

`Runtime: 132 ms, faster than 33.97% of C++ online submissions for Sliding Window Maximum.Memory Usage: 31.1 MB, less than 24.37% of C++ online submissions for Sliding Window Maximum.class Solution {public:    vector<int> maxSlidingWindow(vector<int>& nums, int k) {        vector<int> ret;        priority_queue<pair<int, int>> pq;        const int n = nums.size();        for (int i = 0; i < n; ++i)        {            pq.emplace(nums[i], i);            if (i >= k-1)            {                while (!pq.empty() && pq.top().second < i - k + 1)                {                    pq.pop();                }                ret.push_back(pq.top().first);            }        }        return ret;    }};`

Multiset solution

`Runtime: 220 ms, faster than 10.34% of C++ online submissions for Sliding Window Maximum.Memory Usage: 40.9 MB, less than 7.40% of C++ online submissions for Sliding Window Maximum.class Solution {public:    vector<int> maxSlidingWindow(vector<int>& nums, int k) {        vector<int> ret;        multiset<int> ms;        const int n = nums.size();        for (int i = 0; i < n; ++i)        {            ms.insert(nums[i]);            if (ms.size() == k)            {                ret.push_back(*ms.rbegin());            }            else if (ms.size() > k)             {                //https://stackoverflow.com/questions/9167745/in-stdmultiset-is-there-a-function-or-algorithm-to-erase-just-one-sample-unic                ms.erase(ms.equal_range(nums[i-k]).first);                ret.push_back(*ms.rbegin());            }        }        return ret;    }};`

Using the monotonic queue idea to improve the multiset code

`Runtime: 176 ms, faster than 19.64% of C++ online submissions for Sliding Window Maximum.Memory Usage: 41.1 MB, less than 5.12% of C++ online submissions for Sliding Window Maximum.class Solution {public:    vector<int> maxSlidingWindow(vector<int>& nums, int k) {        vector<int> ret;        multiset<pair<int, int>> ms;        const int n = nums.size();        for (int i = 0; i < n; ++i)        {            ms.emplace(nums[i], i);            if (i >= k-1)            {                while (!ms.empty() && ms.rbegin()->second < (i - k + 1))                {                    ms.erase(--ms.end());                }                ret.push_back(ms.rbegin()->first);                while (!ms.empty() && (nums[i] > ms.begin()->first || ms.begin()->second < i - k +1))                {                    ms.erase(ms.begin());                }            }        }        return ret;    }};`

Actually, we can directly use a deque to implement the monotonic queue solution as shown below:

Monotonic solution. The queue is in increasing order.

`class Solution {public:    vector<int> maxSlidingWindow(vector<int>& nums, int k) {        vector<int> ret;        deque<pair<int, int>> dq;        const int n = nums.size();        for (int i = 0; i < n; ++i)        {                        while (!dq.empty() && nums[i] >= dq.front().first)            {                dq.pop_front();            }            // all the less or equal to current value is poped from left. The unpopped will be the values that are larger than the current one            dq.emplace_front(nums[i], i);            if (i >= k-1)            {                // pop all invalid items from the right                while (!dq.empty() && dq.back().second < i - k + 1)                {                    dq.pop_back();                }                ret.push_back(dq.back().first);            }        }        return ret;    }};`

## decrease deque

`// decrease deque// time complexity: O(n)// Space complexity: O(n)class Solution {public:  int findMaxValueOfEquation(vector<vector<int>>& points, int k) {        deque<pair<int, int>> decrease_dq; // {y - x, x} Sort by y - x.    int ans = INT_MIN;    for (const auto& p : points) {      const int xj = p[0];      const int yj = p[1];      // Remove invalid points, e.g. xj - xi > k      while (!decrease_dq.empty() && xj - decrease_dq.front().second > k)        decrease_dq.pop_front();      if (!decrease_dq.empty())        ans = max(ans, xj + yj + decrease_dq.front().first);             while (!decrease_dq.empty() &&  yj - xj >= decrease_dq.back().first)         decrease_dq.pop_back();      decrease_dq.emplace_back(yj - xj, xj);    }    return ans;  }};`

## increase deque

`// increase dequeclass Solution {public:  int findMaxValueOfEquation(vector<vector<int>>& points, int k) {        deque<pair<int, int>> increase_dq; // {y - x, x} Sort by y - x.    int ans = INT_MIN;    for (const auto& p : points) {      const int xj = p[0];const int yj = p[1];      // Remove invalid points, e.g. xj - xi > k      while (!increase_dq.empty() && xj - increase_dq.back().second > k)increase_dq.pop_back();      if (!increase_dq.empty())ans = max(ans, xj + yj + increase_dq.back().first);            while (!increase_dq.empty() &&  yj - xj >= increase_dq.front().first) increase_dq.pop_front();      increase_dq.emplace_front(yj - xj, xj);    }    return ans;  }};`

## priority queue solution

`// priority queue//time complexity: O(n log n)//space compleixty: O(n)class Solution {public:  int findMaxValueOfEquation(vector<vector<int>>& points, int k) {        priority_queue<pair<int, int>> pq; // {y - x, x} Sort by y - x.    int ans = INT_MIN;    for (const auto& p : points) {      const int xj = p[0];const int yj = p[1];      // Remove invalid points, e.g. xj - xi > k      while (!pq.empty() && xj - pq.top().second > k)pq.pop();      if (!pq.empty())ans = max(ans, xj + yj + pq.top().first);            pq.emplace(yj - xj, xj);    }    return ans;  }};`

## multiset solution A

`class Solution {public:    int findMaxValueOfEquation(vector<vector<int>>& points, int k) {        int res = INT_MIN;        const int n = points.size();        multiset<pair<int, int>, greater<pair<int, int>>> ms;        for (auto p:points){           while (!ms.empty() && p[0]-ms.begin()->second>k)ms.erase(ms.begin());            if(!ms.empty())res = max(res,p[0] +p[1]+ms.begin()->first);            ms.insert({-p[0]+p[1], p[0]});        }        return res;    }};`

## multiset solution B

`//time O(n log n)// space O(n log n)class Solution {public:    int findMaxValueOfEquation(vector<vector<int>>& points, int k) {        multiset<int, greater<int>> ms;        int ans = INT_MIN;        for(int i = 0, j = 0; i < points.size(); ++i){            while(points[i][0] - points[j][0] > k){                ms.erase(ms.find(points[j][1] - points[j][0]));                ++j;            }            if(!ms.empty())                ans = max(ans, points[i][1] + points[i][0] + *ms.begin());            ms.insert(points[i][1] - points[i][0]);        }        return ans;    }};`

see [1]

--

--