An integer array temperatures contains one temperature for each day. Build an answer array where every position stores the number of days before the next strictly warmer temperature. Store 0 when no warmer future day exists.
Example 1
Input: temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0]
Explanation: Temperature 73 waits one day for 74. Temperature 75 waits four days for 76. No warmer future day exists after temperature 76 or the final temperature 73.
Example 2
Input: temperatures = [80, 80, 79]
Output: [0, 0, 0]
Explanation: Equal temperatures are not warmer, and no later value exceeds either temperature 80 or temperature 79.
Brute Force Approach
The simplest method checks the days ahead one by one. The first day with a higher temperature gives the required waiting time, so there is no need to check further for that day.
This search is repeated for every day, which makes the approach easy to understand but inefficient because the same future days may be checked many times.
Algorithm
Initialize an answer array of size
Nwith0, because some days may not have a warmer future day.Traverse each day from left to right.
For every day, start checking from the next day.
Continue moving forward until a temperature strictly greater than the current temperature is found.
Store the index difference as the waiting time.
Stop the search after finding the first warmer day, because it is the nearest one.
Keep the answer as
0if no warmer day exists.Return the completed answer array.
Dry Run
Image 1
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Finds warmer days with direct forward scans. vector<int> dailyTemperatures(vector<int>& temperatures) { int N = temperatures.size(); vector<int> answer(N, 0); // Every day starts an independent search. for (int day = 0; day < N; day++) { // Future days are checked from nearest to farthest. for (int future = day + 1; future < N; future++) { // A strict increase ends the nearest-day search. if (temperatures[future] > temperatures[day]) { // Index distance equals the waiting period. answer[day] = future - day; break; } } } return answer; }};// Driver codeint main() { vector<int> temperatures = {73, 74, 72, 76}; Solution obj; vector<int> answer = obj.dailyTemperatures(temperatures); for (int days : answer) { cout << days << " "; } return 0;}Complexity Analysis
Time Complexity: O(N2), where N is the number of days, because each day may scan all remaining future days in the worst case.
Space Complexity: O(N), because the returned answer array stores N values and no additional growing data structure is used.
Optimal Approach
For every current day, find the nearest future day with a warmer temperature. The search matches the Next Greater Element pattern. A right-to-left traversal keeps already visited future days available, so the stack can offer the nearest warmer candidate directly.
The stack stores only indices, while temperatures are read from the input array. Cooler or equal stack-top days are removed because neither day can be warmer than the current day. The remaining top index, if present, marks the nearest warmer day. Every index enters once and leaves at most once, producing linear work.
Algorithm
Initialize an answer array of size
Nwith zeros and an empty stack because days without warmer candidates must remain0.Traverse temperatures from right to left so every stack index belongs to a future day of the current position.
Compare the current temperature with the temperature found through the stack-top index so unusable future candidates can be removed.
Pop every cooler or equal stack-top day because no removed temperature can answer the current day, and the current day becomes a closer candidate for earlier days.
Store
stackTop - currentDaywhen the stack remains non-empty because the top index gives the nearest future warmer day.Push the current day index so an earlier day can consider the current temperature as a future candidate.
Return the answer array after all days are processed because each position now stores a nearest-warmer distance or the initial value
0.
Dry Run
Daily Temp Optimal
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Finds warmer days with a monotonic stack. vector<int> dailyTemperatures(vector<int>& temperatures) { int N = temperatures.size(); vector<int> answer(N, 0); stack<int> futureDays; // Right-to-left order exposes future candidates. for (int day = N - 1; day >= 0; day--) { // Cooler or equal days cannot be an answer. while (!futureDays.empty() && temperatures[futureDays.top()] <= temperatures[day]) { futureDays.pop(); } // A remaining top is the nearest warmer day. if (!futureDays.empty()) { answer[day] = futureDays.top() - day; } // Earlier days can use the current day. futureDays.push(day); } return answer; }};// Driver codeint main() { vector<int> temperatures = {73, 74, 72, 76}; Solution obj; vector<int> answer = obj.dailyTemperatures(temperatures); for (int days : answer) { cout << days << " "; } return 0;}Complexity Analysis
Time Complexity: O(N), because every day index is pushed once and popped at most once from the monotonic stack.
Space Complexity: O(N), because the answer array and future-index stack can each contain N values.
Interview follow-up Questions
Indices support temperature comparisons through the input array and provide the waiting time through index subtraction.
Be the first to add a comment.