Sliding window min/max, priority queue & Monotonic Queue
7 min readJul 2, 2020
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
Think about a simpler question:
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 is
3
4
5
5
8
10
The solution above is pretty nature and pretty straightforward.
How about make it stupid?
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:
dq
max val sofar3
dq
3
max val sofar4
dq
4
max val sofar5
dq
5
max val sofar5
dq
5
max val sofar8
dq
8
max 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:
i0
max val sofar3
i1
max val sofar4
i2
max val sofar5
i3
max val sofar5
i4
max val sofar8
i5
max 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;
}output
i0
max val sofar3
i1
max val sofar4
i2
max val sofar5
i3
max val sofar5
i4
max val sofar8
i5
max 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;
}
};1499. Max Value of Equation
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 deque
class 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;
}
};
Some similar problems
https://leetcode.com/problems/shortest-unsorted-continuous-subarray/
https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/
https://leetcode.com/problems/next-greater-element-i/
https://leetcode.com/problems/largest-rectangle-in-histogram/
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
A real interview problem
see [1]
