/**
 * https://leetcode.com/problems/daily-temperatures
 * Time O(N) | Space O(N) - result array will always count as extra space
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function (temp) {
    let res = new Array(temp.length).fill(0);
    let stack = [];

    for (let i = 0; i < temp.length; i++) {
        while (stack.length && temp[i] > temp[stack[stack.length - 1]]) {
            let idx = stack.pop();
            res[idx] = i - idx;
        }
        stack.push(i);
    }
    return res;
};

/**
 * https://leetcode.com/problems/daily-temperatures
 * Time O(N) | Space O(N)
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function (temperatures, stack = []) {
    const days = Array(temperatures.length).fill(0);

    for (let day = 0; day < temperatures.length; day++) {
        /* Time O(N + N) */
        while (canShrink(stack, temperatures, day)) {
            /* Time O(N + N) */
            const prevColdDay = stack.pop();
            const daysToWait = day - prevColdDay;

            days[prevColdDay] = daysToWait; /* Ignore Space O(N) */
        }

        stack.push(day); /* Space O(N) */
    }

    return days;
};

const canShrink = (stack, temperatures, day) => {
    const previousDay = stack[stack.length - 1];
    const [prevTemperature, currTemperature] = [
        temperatures[previousDay],
        temperatures[day],
    ];
    const isWarmer = prevTemperature < currTemperature;

    return stack.length && isWarmer;
};

/**
 * https://leetcode.com/problems/daily-temperatures
 * Time O(N) | Space O(1)
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function (temperatures, hottest = 0) {
    const days = new Array(temperatures.length).fill(0);

    for (let day = temperatures.length - 1; 0 <= day; day--) {
        /* Time O(N + N) */
        const temperature = temperatures[day];

        const isHotter = hottest <= temperature;
        if (isHotter) {
            hottest = temperature;
            continue; /* Time O(N + N) */
        }

        search(
            temperatures,
            day,
            temperature,
            days,
        ); /* Time O(N + N) | Ignore Space O(N) */
    }

    return days;
};

const search = (temperatures, day, temperature, days, dayCount = 1) => {
    const isHotter = () => temperatures[day + dayCount] <= temperature;
    while (isHotter()) dayCount += days[day + dayCount]; /* Time O(N + N) */

    days[day] = dayCount; /* Ignore Space O(N) */
};