C# Solution : Finally made it work!


  • 0
    J

    The Idea is to start from Reverse. First I am finding if there is any greater element on the right of a given day. This is used in the second iteration to break the loop whenever I encounter a day for which there is no bigger temp. on the right of it. In the second iteration, I create 2 arrays, one which stores the nearest temperature that is bigger than the current day temperature and its distance from the current day.
    During every comparison, only 2 scenarios exist.

    1. When there is a temperature that is bigger than the current. In that case, the distance is the index - current day index.
    2. I find a temperature that is smaller, and in that case, I find its nearest biggest temperature and start comparing. If I Find a distance that is zero, it means there is no more temp. that is bigger than current. So break.

    Brute force C# fails with TLE. Hence this solution.

    public int[] DailyTemperatures(int[] temperatures)
            {
                if (temperatures == null || temperatures.Length == 0)
                    return null;
    
                int len = temperatures.Length;
    
                var distances = new int[len];
                var temp_max = new int[len];
    
                int max = temperatures[len - 1];
                distances[len - 1] = 0;
    
                for (int i = len - 2; i >= 0; i--)
                {
                    max = Math.Max(max, temperatures[i]);
                    if (max == temperatures[i])
                        distances[i] = 0;
                    else distances[i] = -1;
                }
    
                for (int i = len - 2; i >= 0; i--)
                {
                    int current_max = temperatures[i + 1];
                    int current_index = i + 1;
    
                    while (current_index < len && current_max <= temperatures[i])
                    {
                        if (distances[current_index] == 0)
                        {
                            distances[i] = 0;
                            break;
                        }
                        current_max = Math.Max(current_max, temp_max[current_index]);
                        current_index += Math.Max(1, distances[current_index]);
                    }
                    if (current_max > temperatures[i])
                    {
                        temp_max[i] = current_max;
                        distances[i] = current_index - i;
                    }
                }
                return distances;
            }
    

  • 0
    J

    Other stack based solutions are intuitive. This is complicated!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.