[Google][LeetCode] Daily Temperatures

Problem: Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

Example:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Approach: We can use stack here. We will keep pushing the index of temperature into the stack till we find lesser temperature then the top of the stack otherwise we just found the next greater temperature and we keep popping the temperatures which are less than the current temperature. While popping we just take the difference between current_index and popped index and write it to output array's current_index.

Implementation in C#:

    public int[] DailyTemperatures(int[] temperatures)

    {

        int length = temperatures?.Length ?? 0;

        if (length == 0)

        {

            return new int[] {};

        }

        if (length == 1)

        {

            return new int[] {0};

        }

        Stack<int> stack = new Stack<int>();

        int[] result = new int[length];

        for (int i = length - 1; i >= 0; --i)

        {

            while (stack.Count > 0 &&

                   temperatures[stack.Peek()] <= temperatures[i])

            {

                stack.Pop();

            }

            if (stack.Count == 0)

            {

                result[i] = 0;  

            }

            else

            {

                result[i] = stack.Peek() - i;

            }  

            stack.Push(i);

        }

        return result;

    }

Complexity: O(n)