algoadvance

Leetcode 739. Daily Temperatures

Problem Statement

You are given an array of integers temperatures represents the daily temperatures. Return an array answer such that answer[i] is the number of days you have to wait after the i-th day to get a warmer temperature. If there is no future day for which this is possible, put 0 instead.

Clarifying Questions

  1. Is it possible for the temperatures array to be empty?
    • No, there will be at least one temperature in the array.
  2. Can the temperatures have negative values?
    • Yes, it’s possible, but typically temperatures are non-negative integers.
  3. What is the range for the number of days (i.e., the length of the temperatures array)?
    • The input size can range from 1 to 100,000.

Strategy

To solve this problem efficiently, we can use a stack to keep track of the indices of the temperature array. By iterating through the array once, we push the indices onto the stack when the current day’s temperature is not warmer than the temperature at the index on the top of the stack. When we find a day that is warmer, we calculate the difference between the current index and the index on the top of the stack. We then update our answer array accordingly and continue.

Here’s how we can do it:

  1. Initialize an empty stack to hold indices.
  2. Initialize the answer array with zeros of the same length as temperatures.
  3. Iterate over each temperature. For each temperature, perform the following:
    • While the stack is not empty and the current temperature is greater than the temperature at the index stored at the top of the stack:
      • Pop the index from the stack.
      • Calculate the difference between the current index and the popped index to find the number of days until a warmer temperature.
      • Update the answer array at the popped index with this difference.
    • Push the current index onto the stack.
  4. Return the answer array.

Code

#include <vector>
#include <stack>

std::vector<int> dailyTemperatures(std::vector<int> &temperatures) {
    int n = temperatures.size();
    std::vector<int> answer(n, 0);
    std::stack<int> indices;  // stack to store indices of temperatures

    for (int i = 0; i < n; ++i) {
        while (!indices.empty() && temperatures[i] > temperatures[indices.top()]) {
            int idx = indices.top();
            indices.pop();
            answer[idx] = i - idx;
        }
        indices.push(i);
    }

    return answer;
}

Time Complexity

The time complexity of this solution is (O(n)), where (n) is the number of days (or the length of the temperatures array). Each element is pushed and popped from the stack at most once, making the overall time complexity linear.

Space Complexity

The space complexity is (O(n)) due to the use of the stack which stores indices of temperatures and the answer array which holds the result.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI