Daily Temperatures - Miscellaneous / Monotonic Stack

Problems
1

https://algo.monster/problems/daily_temperatures

2

Thanks for the explanation. One could also go left to right (no reverse needed):

def daily_temperatures(t: List[int]) → List[int]:
stack = []
res = [0] * len(t)
# going left to right, while maintaining a max stack. If incoming t is greater than top of stack,
# for each element popped, the answer is (idx of incoming - idx of popped)
for idx,ele in enumerate(t):
while stack and t[stack[-1]] < ele:
popped = stack.pop()
res[popped] = idx - popped
stack.append(idx)
return res

3

There’s a better way to do this without needing to iterate over temperatures in reverse and then reverse the result. You can initialize the results arr equal to the length of t filled with 0 and initialize an empty stack that will store indices. Then iterate over t using indices. While the stack isn’t empty and the number the top of the stack points to is less than the current number, pop it, and set the corresponding index in the results array to the difference between the current number’s index and the popped index. e.g. If temps are 71, 70, 68, 75, when you get to 75, the top of the stack will be 68 with an index of 2 and the difference between the current index 3 and 2 is just 1. So you go to results[2] and set it to 1. This way you only ever need to iterate over everything once in linear time.

function dailyTemperatures(t) {
    const res = Array(t.length).fill(0);
    const stack = [];
    
    for (let i = 0; i < t.length; i++) {
        while (stack.length > 0 && t[stack[stack.length - 1]] < t[i]) {
            const prevDayIndex = stack.pop();
            res[prevDayIndex] = i - prevDayIndex;
        }
        stack.push(i);
    }
    
    return res;
}
4

there is no need to iterate over the temperatures in reverse and also there is lot of computations which doesn’t fit to the “Monotonic Stack template”, the below code fits to the template and easily understandable .

res = [0] * len(t)
    stack = [] #stores[temp, index]
    for i, temp in enumerate(t):
        while stack and stack[-1][0] < temp:
            stackT, stackI = stack.pop()
            res[stackI] = (i-stackI)
        stack.append((temp, i))
    
    return res
5

How is this not O(n^2)? n outer loops, and worst case cn inner loops.

6

I see it now… Every element is pushed exactly once, and popped (obviously) no more than once.

7

We don’t need to keep updating previous indecies if we start from the last day

using namespace std;

std::vector<int> daily_temperatures(std::vector<int> t) {
    // WRITE YOUR BRILLIANT CODE HERE
    std::vector<int> res(t.size(), 0);
    std::vector<int> stack;
    for (int i = t.size() - 1; i >= 0; i-- ){
        while (!stack.empty() && t[i] >= t[stack.back()]) {
            stack.pop_back();
        }
        
        if (!stack.empty()) {
            res[i] = stack.back() - i;
        }
        stack.push_back(i);
    }
    return res;
}
8

exactly