This is an effort to document how I learned one of the most challenging concepts (which looks so easy at first glance) after Backtracking, which is Monotonically Increasing/Decreasing Stack and Queue problems.
These are challenging because it's not always apparent that using this data structure makes the solution any more accessible. So, let's start with the different patterns I have seen and break them down.
Note: The reason I write these articles is two folds: (1) Showing that Rust is a fine language to do leetcode in, (2) Keep track of the problems and their solutions so that anyone can practice these several times to build muscle memory around the techniques being used.
In this pattern, you track the element index for which we need an event in the future. So, as we iterate over the input array, we first see if the current temperature is the next bigger element than the elements found previously. Then, we store the current index and the temperature in the Monotonically Decreasing Stack to see if we can find an element bigger than the current temperature on the right as we iterate over the rest of the input array.
impl Solution {
pub fn daily_temperatures(temperatures: Vec<i32>) -> Vec<i32> {
let (mut stk, mut res) = (Vec::<(i32, usize)>::new(), vec![0]);
res.resize(temperatures.len(), 0);
for (idx, temperature) in temperatures.iter().enumerate() {
while stk.len() > 0 && stk[stk.len() - 1].0 < *temperature {
res[stk[stk.len() - 1].1] = (idx - stk[stk.len() - 1].1) as i32;
stk.pop();
}
stk.push((*temperature, idx));
}
res
}
}In this pattern, you must use 2 separate steps to find the optimal solution. First, you find all the relevant ith elements from the left and track them in a Monotonically Decreasing Stack, and then find the relevant jth elements from the right as you calculate the maximum length of the ramp that can be formed between the ith and jth elements.
Input: [6,0,8,2,1,5]
If you see carefully, the relevant ones are:
num1, num2 -> idx1, idx2 -> width
6, 8 0, 2 2
0, 8 1, 2 1
0, 2 1, 3 2
0, 1 1, 4 3
0, 5 1, 5 4
2, 5 3, 5 2
1, 5 4, 5 1
Now, here even though we can create the ramps 7 ways, we can see:
0, 8
0, 2
0, 1
Are not useful as we have a bigger element than 0 (which is 5) after all these.
Similarly,
2, 5
1, 5
Are also not relevant as we a smaller element than 2 and 1 (which is 0) before all these.
So, we can use a Monotonic Decreasing Stack to keep track of the elements 6, 0
which will be the only ith elements we care about.
Step 1:
-------
We iterate over each element, and if we encounter an element less than the top
element in the Monotonically Decreasing Stack, we add it in.
for (i, elem) in input.iter().enumerate() {
if stack.len() == 0 || stack[stack.len() - 1].0 > elem {
stack.push((elem, i))
}
}
Step 2:
-------
We iterate over each element, now from the right and if we encounter an element less than the top
element in the Monotonically Decreasing Stack, we calculate the maximum width, else we keep popping.
let mut maximum_width = 0;
for j in (0..(nums.len())).rev() {
while stack.len() > 0 && stack[stack.len() - 1].0 <= input[j] {
let i = stack[stack.len() - 1].1;
maximum_width = std::cmp::max(maximum_width, j - i);
stack.pop();
}
}
So here is the final solution:
impl Solution {
pub fn max_width_ramp(nums: Vec<i32>) -> i32 {
let (mut maximum_width, mut stk) = (0, Vec::<(i32, usize)>::new());
for (i, num) in nums.iter().enumerate() {
if stk.len() == 0 || *num < stk[stk.len() - 1].0 {
stk.push((*num, i))
}
}
for j in (0..(nums.len())).rev() {
while stk.len() > 0 && nums[j] >= stk[stk.len() - 1].0 {
let i = stk[stk.len() - 1].1;
maximum_width = std::cmp::max(maximum_width, j - i);
stk.pop();
}
}
maximum_width as i32
}
}1856. Maximum Subarray Min-Product
This problem is relatively easy as you understand the 2 steps involved. First, you keep track of the increasing numbers in the input array in a monotonically increasing stack, and then in the next step, you have to unwind the stack to calculate the maximum min-product.
impl Solution {
pub fn max_sum_min_product(nums: Vec<i32>) -> i32 {
const MOD: u64 = 1e9 as u64 + 7;
let mut stk = Vec::<(u64, u64, usize)>::new();
let mut maximum = 0u64;
// Step 1: Build the Monotonically Increasing Stack
for (idx, num) in nums.iter().enumerate() {
if stk.len() == 0 || stk[stk.len() - 1].0 <= (*num as u64) {
stk.push((*num as u64, *num as u64, idx));
maximum = std::cmp::max(
maximum,
(*num as u64)
);
} else {
let (mut current_sum, mut current_idx) = (0, 0);
while stk.len() > 0 && stk[stk.len() - 1].0 > (*num as u64) {
current_sum = current_sum + stk[stk.len() - 1].1;
current_idx = stk[stk.len() - 1].2;
let current_num = stk[stk.len() - 1].0;
maximum = std::cmp::max(
maximum,
current_sum * current_num
);
stk.pop();
}
stk.push((*num as u64, (*num as u64) + current_sum, current_idx));
}
}
// Step 2: Unwind the stack to calculate the maximum
let mut current_sum = 0u64;
while stk.len() > 0 {
current_sum += stk[stk.len() - 1].1;
maximum = std::cmp::max(
maximum,
current_sum * stk[stk.len() - 1].0
);
stk.pop();
}
(maximum % MOD) as i32
}
}This problem is hard if you don’t know the trick, as it combines Prefix Sum, Suffix Sum, and Monotonically Increasing Stack problems.
First, we calculate the sums of the height of towers possible on the left by considering each element of the max_heights to be the peak element. The trick to understand here is the previous element can be less, equal, or greater. We can extend the prefix sum if the previous element is less or equal. But if the previous element was greater, then unfortunately, we need to look back to the previous element that was smaller than the current element, which can then be extended. This, by definition, becomes a Monotonically Increasing Stack problem.
Input = [5,3,4,1,1]
Stk = []
LeftPrefixSums = [0,0,0,0,0]
Index 1:
There are no previous element, so we just add the max_height in PrefixSums.
LeftPrefixSums = [5,0,0,0,0]
Stk = [(5,0)]
Index 2:
The current element is smaller than the previous element, so we pop out.
Stk = []
And we also don't find any element in the stack, so we just multiply:
(idx + 1) * max_height
And put that into the stack.
LeftPrefixSums = [5,6,0,0,0]
Stk = [(3,1)]
Index 3:
The current element is greater than the previous element, so we can continue
extending.
And we just add the PrefixSum of the previous element + current max_height.
LeftPrefixSums = [5,6,10,0,0]
Stk = [(3,1), (4,2)]
Index 4:
The current element is smaller than the previous element,
so we keep popping out.
Stk = []
And we also don't find any element in the stack, so we just multiply:
(idx + 1) * max_height
And put that into the stack.
LeftPrefixSums = [5,6,10,4,0]
Stk = [(1,3)]
Index 5:
The current element is equal so we can extend.
LeftPrefixSums = [5,6,10,4,5]
Stk = [(1,3),(1,4)]
Second, we calculate the sums of the height of towers possible on the right by considering each element of the max_heights as the peak element. We use a similar approach to what we used in building the previous prefix sum array.
Input = [5,3,4,1,1]
Stk = []
RightPrefixSums = [0,0,0,0,0]
Index 1:
There are no previous element, so we just add the max_height in PrefixSums.
RightPrefixSums = [0,0,0,0,1]
Stk = [(1,4)]
Index 2:
The current element is equal to the next element, so we can extend.
RightPrefixSums = [0,0,0,2,1]
Stk = [(1,4),(1,3)]
Index 3:
The current element is greater than the previous element, so we can continue
extending.
And we just add the PrefixSum of the next element + current max_height.
RightPrefixSums = [0,0,6,1,1]
Stk = [(1,4),(1,3),(4,2)]
Index 4:
The current element is smaller than the next element,
so we keep popping out.
Stk = [(1,4),(1,3)]
We found the element that is smaller to the right, or next,
for rest we multiply:
(stk[-1].1 - idx) * max_height
And put that into the stack.
RightPrefixSums = [0,8,6,1,1]
Stk = [(1,4),(1,3),(3,1)]
Index 5:
The current element is greater than the next element, so we extend.
RightPrefixSums = [13,8,6,1,1]
Stk = [(1,4),(1,3),(3,1),(5,0)]Then, iterate over the max_heights array to calculate the maximum sum possible.
Here is the final solution.
impl Solution {
pub fn maximum_sum_of_heights(max_heights: Vec<i32>) -> i64 {
let mut lConfigurations = Vec::<i64>::new();
lConfigurations.resize(max_heights.len(), 0);
let mut rConfigurations = Vec::<i64>::new();
rConfigurations.resize(max_heights.len(), 0);
let mut stk = Vec::<(i32, usize)>::new();
for (idx, &height) in max_heights.iter().enumerate() {
while stk.len() > 0 && stk[stk.len() - 1].0 > height {
stk.pop();
}
if stk.len() > 0 {
lConfigurations[idx] += lConfigurations[stk[stk.len() - 1].1];
lConfigurations[idx] += ((idx - stk[stk.len() - 1].1) as i64) * (height as i64);
} else {
lConfigurations[idx] += ((idx + 1) as i64) * (height as i64);
}
stk.push((height, idx));
}
stk = Vec::<(i32, usize)>::new();
for (idx, &height) in max_heights.iter().enumerate().rev() {
while stk.len() > 0 && stk[stk.len() - 1].0 > height {
stk.pop();
}
if stk.len() > 0 {
rConfigurations[idx] += rConfigurations[stk[stk.len() - 1].1];
rConfigurations[idx] += ((stk[stk.len() - 1].1 - idx) as i64) * (height as i64);
} else {
rConfigurations[idx] += ((rConfigurations.len() - idx) as i64) * (height as i64);
}
stk.push((height, idx));
}
let mut res = -1;
for (idx, &height) in max_heights.iter().enumerate() {
res = std::cmp::max(
res,
lConfigurations[idx] + rConfigurations[idx] - (height as i64)
);
}
res
}
}This is another interesting problem requiring a unique idea that requires us to track the decreasing number and the minimum number that we saw before the top element in the same monotonically decreasing stack. This is a very tricky question, and it isn't easy to code it correctly even if you understand the solution, though the solution is not that large.
Here is what the steps would look like:
Input = [2, 4, 1, 2, 3]
Stk = [(<monotonically_decreasing_element>, <minimum_element_left>)]
Index 0:
We don't have any minimum, so let's take
the current element at index 0 as the minimum.
Stk = [(2,2)]
There is just 1 element in the stack so we continue.
Index 1:
Now the element is bigger than the element at the top of the stack, so we pop.
Stk = []
Now the minimum element to the left is minimum of 2 and 4. So we add,
Stk = [(4,2)]
Index 2:
Next element is smaller than the top element on the stack, so we will just
add the current element and calculate the minimum. But before that,
Now that we also have an element in the stack, we need to see if the criteria is met.
minimum_element_left < current_element < element_at_the_top_of_the_stack.
2 < 1 < 4 # This is incorrect so criteria not met.
Stk = [(4,2),(1,2)]
Index 3:
Now the next element is bigger than the element at the top of the stack,
so we pop.
Stk = [(4,2)]
Now we still have more than 1 element, so lets check the criteria.
2 < 2 < 4 # This is incorrect so criteria not met.
Stk = [(4,2),(2,2)]
Index 4:
Now the next element is bigger than the element at the top of the stack,
so we pop.
Stk = [(4,2)]
As we still have more than 1 element, so lets check the criteria.
2 < 3 < 4 # Yes we have found the final element.
Return TrueAnd here is the final code in Rust:
impl Solution {
pub fn find132pattern(nums: Vec<i32>) -> bool {
let (mut stk, mut minimum) = (Vec::<(i32, i32)>::new(), nums[0]);
for num in nums {
while stk.len() > 0 && stk[stk.len() - 1].0 <= num {
stk.pop();
}
if stk.len() > 0 && num > stk[stk.len() - 1].1 {
return true;
}
stk.push((num, minimum));
minimum = std::cmp::min(minimum, num)
}
return false;
}
}2289. Steps to Make Array Non-decreasing
This problem is again very difficult to come up with, even if you know it requires a Monotonically Decreasing Stack. Like the above problem, you need to keep track of the number itself in the stack, and how many steps were completed before this number came up needs to be tracked.
impl Solution {
pub fn total_steps(nums: Vec<i32>) -> i32 {
let mut stk = Vec::<(i32, i32)>::new();
for &num in nums.iter().rev() {
let mut times = 0;
while stk.len() > 0 && num > stk[stk.len() - 1].0 {
times = std::cmp::max(times + 1, stk[stk.len() - 1].1);
stk.pop();
}
stk.push((num, times));
}
let mut maximum = 0;
for elem in stk {
maximum = std::cmp::max(
maximum,
elem.1
);
}
maximum
}
}This problem involves using a Monotonically Decreasing Queue instead of a Stack. The specialty of this data structure is that you compare against the top element while you add or remove it from the back of the queue.
You can try this problem using Dynamic Programming but the O(n*k) solution will cause TLE. So, we need to bring it down from k to something manageable. This is possible if we skip comparing all k elements and rather jump to the greater element's index. This can be done using a Monotonically Decreasing Queue, which we can implement using a Deque.
Input = [1,-5,-20,4,-1,3,-6,-3]
k = 2
n = Length of the input = 8
DP = [0,0,0,0,0,0,0,-3]
Deque = [7] # We will be keeping the index in here, rather than the elements
We will then walk from the right to the left.
Index 6:
We compare the top element stored on the deque and store in DP and Deque:
DP[6] = Input[6] + DP[7] # 7 is the top index in the Deque
DP = [0,0,0,0,0,0,-9,-3]
Deque = [7,6]
Index 5:
DP[5] = Input[5] + DP[7]
DP = [0,0,0,0,0,0,-9,-3]
Deque = [5,7,6]
Index 4:
DP[4] = Input[4] + DP[5]
DP = [0,0,0,0,-1,0,-9,-3]
Deque = [5,4,7,6]
Index 3:
DP[3] = Input[3] + DP[5]
DP = [0,0,0,4,-1,0,-9,-3]
Deque = [3,5,4,7,6]
Index 2:
DP[2] = Input[2] + DP[3]
DP = [0,0,-16,4,-1,0,-9,-3]
Deque = [3,5,4,7,6,2]
Index 1:
DP[1] = Input[1] + DP[3]
DP = [0,-1,-16,4,-1,0,-9,-3]
Now something interesting is going to happen, we need to pop elements from the
back to keep the queue in Decreasing order.
Deque = [3,5,4,1]
Index 0:
Now another interesting thing we need to do is we need to pop elements from
the front that is beyond Index + k = 0 + 2 = 2:
Deque = [1]
Then we calculate,
DP[0] = Input[0] + DP[1]
DP = [0,-1,-16,4,-1,0,-9,-3]
And finally the result is DP[0] = 0.Here is the final code:
use std::collections::VecDeque;
impl Solution {
pub fn max_result(nums: Vec<i32>, k: i32) -> i32 {
let n = nums.len();
let mut dp = vec![0];
dp.resize(n, 0);
dp[n - 1] = nums[n - 1];
let mut q = VecDeque::<usize>::new();
q.push_back(n - 1);
for i in (0..n-1).rev() {
while q.front().unwrap() - i > (k as usize) {
q.pop_front();
}
dp[i] = nums[i] + dp[*q.front().unwrap()];
while q.len() > 0 && dp[*q.back().unwrap()] < dp[i] {
q.pop_back();
}
q.push_back(i);
}
dp[0]
}
}Bonus
I am including these problems here because they require other steps before you can use Monotonic Stack or Queue. But using Monotonic Stack or Queue is pretty straightforward if you can get to the first step.
1996. The Number of Weak Characters in the Game
To solve this, you first need to sort the input by the first element in the ascending order and then by the second element in the descending order. After that, you can maintain a Monotonic Decreasing Stack where the elements will have the first element in the Increasing order while the second element will be in the Decreasing order in the Stack.
impl Solution {
pub fn number_of_weak_characters(mut properties: Vec<Vec<i32>>) -> i32 {
properties.sort_unstable_by(|a, b| {
if a[0] != b[0] {
a[0].cmp(&b[0])
} else {
b[1].cmp(&a[1])
}
});
let (mut stk, mut res) = (Vec::<&Vec<i32>>::new(), 0);
for i in 0..properties.len() {
while stk.len() > 0 && stk[stk.len()-1][1] < properties[i][1] {
stk.pop();
res += 1;
}
stk.push(&properties[i]);
}
res
}
}This problem is very easy to implement but hard to get to in terms of the solution. We need to create a Monotonically Increasing Stack of digits till we run out of k digits to remove.
impl Solution {
pub fn remove_kdigits(num: String, k: i32) -> String {
let (mut stk, mut _k) = (Vec::<char>::new(), k);
for digit in num.chars() {
let digit_in_u32: u32 = digit.to_digit(10).unwrap();
while stk.len() > 0 && _k > 0 {
let top = stk[stk.len() - 1].to_digit(10).unwrap();
if top <= digit_in_u32 {
break;
}
_k -= 1;
stk.pop();
}
stk.push(digit);
}
while _k > 0 {
stk.pop();
_k -= 1;
}
// !----- These can be done better. May be with a deque ----!
stk.reverse();
while stk.len() > 0 && stk[stk.len() - 1] == '0' {
stk.pop();
}
stk.reverse();
// !----------- Till here ---------!
if stk.len() == 0 {
stk.push('0');
}
stk.iter().collect()
}
}
