Monotonic Queue Questions
Let's solve the problem related to the monotonic queue patterns.
A monotonic queue means the queue that contains the elements is sorted in increasing or decreasing order. This is used to determine the window's minimum or maximum elements.
A monotonic queue keeps track of elements in increasing or decreasing order, so this should be used when we don’t need to insert the elements between the elements in the queue. This means we should push the current element back to the queue after dropping the smaller or larger elements from the back to keep the order. This implies that we don’t need to use the dropped elements anymore.
Let’s solve some problems to practice a monotonic queue.
Problem 1: Sliding Window Maximum
In this problem, we should find the maximum elements of a fixed window. This means we should keep track of the largest element as we iterate the elements. We should find a way to find the next largest element if we drop the current largest element.
Let’s see the example.
nums = [1, -1, 10, 2, 11, 3, 7, 5] , k = 3
The window size is 3, so we can start getting the maximum value since we iterate at least 3 elements.
1st window is
[1, -1, 10]. The maximum value is 10.2nd window is
[-1, 10, 2]. The maximum value is 10.3rd window is
[10, 2, 11]. The maximum value is 11.4th window is
[2, 11, 3]. The maximum value is 11.5th window is
[11, 3, 7]. The maximum value is 11.6th window is
[3, 7, 5]. The maximum value is 7.
So, the answer should be
[10, 10, 11, 11, 11, 7].
To solve the problem, we can use a monotonic queue for keeping the largest numbers.
For every element, check if any elements in the queue are smaller than or equal to nums[i]. It’s because after we put nums[i] to the window, elements smaller than or equal to nums[i] won’t be used as the maximum value.
Put nums[i] to the back of the monotonic queue. If the queue is empty, then nums[i] is the largest number in the window. If not, there is an element larger than nums[i].
Check if the position of the first element in the queue is out of the window. If the largest number is out of the window, we should pop it from the queue. We can check this by adding the index(i), not the value(nums[i]) to the queue.
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> ans;
const int n = (int)nums.size();
deque<int> q;
for (int i = 0; i < n; ++i) {
while(!q.empty() && nums[q.back()] <= nums[i]) {
q.pop_back();
}
q.push_back(i);
while(!q.empty() && q.front() < i-k+1) {
q.pop_front();
}
if (i >= k-1) {
ans.push_back(nums[q.front()]);
}
}
return ans;
}
};Problem2: K Empty Slots
In this problem, you should find the minimum number of days when two bulbs are turned on and all bulbs between them are turned off.
This problem seems tricky if you keep track of the bulbs’ status. We cannot track the status of every bulb between two turned-on bulbs. However, we can think of the final status of what we want to find.
What we want to find is the following situation.
If K == 3, then
[On, Off, Off, Off, On].If K == 0, then
[On, On].
So, we can ensure this happens when the minimum number of days to turn on any of the K bulbs is later than the maximum number of days to turn on both the left and right bulbs. Based on the input, we can calculate the days to turn on each bulb.
For example, let’s assume that the array that represents the days to turn on the bulbs is [1,3,4,5,2]. It means that it takes 1 day to turn on the first bulb and 3 days to turn on the second day.
On the first day, the bulb status is
[On, Off, Off, Off, Off].On the second day, the bulb status is
[On, Off, Off, Off, On].This can be proved by calculating the following condition.
min({arr[1], arr[2], arr[3]}) > max(arr[0], arr[4])
class Solution {
public:
int kEmptySlots(vector<int>& bulbs, int k) {
const int n = (int)bulbs.size();
vector<int> on(n);
for (int i = 0; i < n; ++i) {
on[bulbs[i]-1] = i+1;
}
int ans = 1e9;
deque<int> q;
for (int i = 0; i < n; ++i) {
while(!q.empty() && on[q.back()] >= on[i]) {
q.pop_back();
}
q.push_back(i);
while(!q.empty() && q.front() <= i-k) {
q.pop_front();
}
if (i >= k && i-k >= 0 && i+1 < n){
int maxOn = max(on[i-k], on[i+1]);
if (k == 0 || maxOn < on[q.front()]) {
ans = min(ans, maxOn);
}
}
}
return ans == 1e9 ? -1 : ans;
}
};Problem3: Minimum Number of Coins for Fruits II
We should find the minimum number of coins needed to buy all the fruits. If we buy the fruit in the index X, we can get the following (X+1) fruits for free. This might be helpful because buying expensive fruits with a small number of coins is possible.
We can use the dynamic programming technique to get the minimum number of coins at each index.
Suppose that dp[i] means the minimum number of coins needed to buy all fruits after (including) index i. Then, we make the following formula.
dp[i] = min(dp[j] + prices[i]) for all j where i<= j <= min(i+i+2, n).
dp[n] should be 0. This is needed because we can buy the fruits at index i, and all fruits after i are free.
This technique works when the price length (n) is small. Here’s the question that you can try with dynamic programming.
However, in this problem, the maximum size of n is 10^5, so it is not fast enough to use dynamic programming. So, we should find another way.
Looking at the formula above, you will see that we don’t need to know all the dp[j] values. We need the minimum dp[j] within the valid window. For example, if the current index is 5, then we should know the minimum of dp[j] where 6 <= j <= 12(5 + 5 + 2).
So, we can use the monotonic queue to keep track of the minimum value of dp[j] and remove the elements outside the window before calculating the dp[i] value. To make this work, we should iterate from the back.
class Solution {
public:
int minimumCoins(vector<int>& prices) {
const int n = (int)prices.size();
vector<int> dp(n+1, 0);
deque<int> q;
q.push_back(n);
for (int i = n-1; i>=0; --i) {
while(!q.empty() && q.front() > i + i + 2) q.pop_front();
dp[i] = prices[i] + dp[q.front()];
while(!q.empty() && dp[q.back()] >= dp[i]) {
q.pop_back();
}
q.push_back(i);
}
return dp[0];
}
};Problem4: Count Non-Decreasing Subarrays After K Operations
We should find the non-decreasing subarrays after most K operations. In this case, the operation is increasing one of the elements by 1 in the subarray. This means that we should make every element bigger within the subarray.
Let’s assume that the nums = [6,3,1,2].
If the subarray is [6,3], it should be [6,6], and the number of operations is 3.
To make 3 to 6 → 3 operations.
If the subarray is [6,3,1], it should be [6,6,6], and the number of operations is 8.
To make 3 to 6 → 3 operations.
To make 1 to 6 → 5 operations.
If the subarray is [3,1,2], it should be [3,3,3], and the number of operations is 3.
To make 1 to 3 → 2 operations.
To make 2 to 3 → 1 operations.
So, when we iterate the elements, we should know how many operations we need to make nums[i] to something. We can use the monotonic queue to store the maximum numbers within the window and add maximum number - nums[i] operations. If the current value is the maximum, the result will be 0.
If the current sum of operations is larger than K, all subarrays containing the current window are invalid. For example, if the nums = [A, B, C, D, E], and the subarray [A, B, C] is invalid. Then [A, B, C, D] and [A, B, C, D, E] are also invalid because they contain the invalid subarray. To calculate the number of invalid subarrays, we can subtract the current index from N(the size of nums).
The hard part is calculating the operations when we reduce the window size. If we find the invalid subarray, we should remove the leftmost value from the window to minimize the operations. In this case, all operation counts should be changed because some of the elements in the window are larger than the next leftmost element.
Let’s say the leftmost element index is L.
If nums[L] <= nums[L+1], then we don’t need to re-calculate the number of operations because nothing will be changed.
If nums[L] > nums[L+1], then we should change the number of operations.
For example, the invalid subarray is [6,3,1,5,10], and L = 0.
Now, nums[1] (3) < num[0] (6).
Find the next element’s index whose value is larger than or equal to nums[0]. It should be 4(nums[4] = 10).
Reduce all operations added from 0 <= i < 4 to make elements to 6.
Now, reduce the window size by changing L to 1.
We should re-calculate operations to make it non-descreasing within 1 <= i < 4.
Find the next element’s index whose value is larger than or equal to nums[1]. It should be 3(nums[3] = 5).
Add all operations to make elements to 3 within 1 <= i < 3.
Add all operations to make elements to 5 within 3 <= i < 4.
To calculate the operations faster, we can pre-calculate the prefixSum array and the right-closest index array to contain the index whose value is larger than or equal to the current value.
To calculate the whole operations from L <= i <= R.
nums[L] * (R - L + 1) - (PrefixSum[R] - PrefixSum[L-1])This calculation is only valid if the elements within the range are non-increasing.
class Solution {
public:
long long countNonDecreasingSubarrays(vector<int>& nums, int k) {
const int n = (int)nums.size();
vector<long long> pref(n+1, 0LL);
vector<int> R(n, n);
stack<int> st;
for (int i = 1; i <= n; ++i) {
pref[i] += pref[i-1] + nums[i-1];
while(!st.empty() && nums[st.top()] <= nums[i-1]) {
R[st.top()] = i-1;
st.pop();
}
st.push(i-1);
}
auto calc = [&] (int l, int r) {
long long cnt = r - l + 1;
return nums[l] * cnt - (pref[r+1] - pref[l]);
};
deque<int> q;
long long tot = ((long long) n * (n + 1)) / 2;
long long invalid = 0LL;
int l = 0, cur = 0;
for (int i = 0; i < n; ++i) {
while(!q.empty() && nums[q.back()] <= nums[i]) {
q.pop_back();
}
q.push_back(i);
cur += nums[q.front()] - nums[i];
while (cur > k) {
invalid += n-i;
int nx = min(R[l], i + 1);
cur -= calc(l, nx-1);
int j = l+1;
while(j < nx) {
cur += calc(j, min(R[j], i + 1)-1);
j = min(R[j], i + 1);
}
l++;
}
while(!q.empty() && q.front() < l) {
q.pop_front();
}
}
return tot - invalid;
}
};Problem5: Shortest Subarray with Sum at Least K
In this problem, we should find the shortest subarray among subarrays where the sum of elements is larger than or equal to K.
To make it easier, we can pre-calculate the prefix sum and find the matching subarrays by calculating the prefixSum[i] - prefixSum[j]. But this algorithm takes too long because we should iterate the input array for each index i. The time complexity is O(N^2).
What we should do in the solution above is to find the maximum of j where the condition meets(prefixSum[i] - prefixSum[j] >= k). The important thing is that if we find the j, we no longer need the prefixSum[j] value. It’s because if we should use it again, then it would be from prefixSum[x] where i < x, and that can’t be the answer.
Also, we don’t need to consider the case where prefixSum[x] >= prefixSum[y] (x < y) when we find the index j. It’s because if x is possible to use, then y is also possible, and y will be used to get the correct answer as we need the shortest subarray.
So, we can use a monotonic queue to keep track of the prefixSum values in increasing order.
If the current prefixSum[i] is smaller than the largest value in the element, then pop the last value from the queue.
If prefixSum[i] - (smallest value from the queue) >= k, then calculate the subarray size.
Pop the smallest value from the queue and check if the condition meets with the next smallest value.
We should keep doing this until the condition is met.
This is because the smallest prefixSum doesn’t ensure the shortest subarray.
class Solution {
public:
int shortestSubarray(vector<int>& nums, int k) {
const int n = (int)nums.size();
vector<long long> pref(n+1, 0LL);
for (int i = 1; i <= n; ++i) {
pref[i] = pref[i-1] + nums[i-1];
}
deque<int> q;
q.push_back(0);
int ans = 1e9;
for (int i = 1; i <= n; ++i) {
while(!q.empty() && pref[q.back()] >= pref[i]) {
q.pop_back();
}
q.push_back(i);
while(!q.empty() && pref[i] - pref[q.front()] >= k) {
ans = min(ans, i - q.front());
q.pop_front();
}
}
return ans == 1e9 ? -1: ans;
}
};Problem6: Constrained Subsequence Sum
We should find the maximum sum of subsequences that meet the condition. The condition is simple. We cannot choose two elements consecutively where the difference between two indices is larger than K. (j - I <= k, where i < j).
This means we should find the maximum sum from the index range [i-k, i-1] to get the maximum sum in the index i. So, we can use the monotonic queue to keep track of the maximum sum in each index in decreasing order.
We can drop the element from the front if the index is smaller than i-k.
We need to consider that use the nums[i] itself without adding something from the queue. This is valid if the largest sum is negative.
If the maximum sum in the current index is larger than any element in the queue, remove that element from the queue.
class Solution {
public:
int constrainedSubsetSum(vector<int>& nums, int k) {
const int n = (int)nums.size();
deque<int> q;
int ans = -1e9;
for (int i = 0; i < n; ++i) {
while(!q.empty() && q.front() < i-k) {
q.pop_front();
}
nums[i] += (q.empty() ? 0 : max(0, nums[q.front()]));
ans = max(ans, nums[i]);
while(!q.empty() && nums[q.back()] <= nums[i]) {
q.pop_back();
}
q.push_back(i);
}
return ans;
}
};