We are given an array of temperatures `T` and are required to return an array `ans` such that `ans[i]` is equal to distance between `i` and the next greater element. If no greater element than `T[i]` exists after `i`th index, `ans[i] = 0`\n\n---\n\n***\u274C Solution - I (Brute-Force)***\n\nLet\'s see how we can solve this using brute-force approach. \n\n* For each index `i`, we can just iterate over the array till we either find the the 1st index `j` such that `T[j] > T[i]` or reach the end of array. \n* If we find `j` such that `T[j] > T[i]`, we have `ans[i] = j-i`.\n* Otherwise, `ans[i] = 0`\n\n**C++**\n```cpp\nclass Solution {\npublic:\n vector dailyTemperatures(vector& T) {\n vector ans(size(T));\n for(int i = 0; i < size(T); i++) \n for(int j = i+1; j < size(T) && !ans[i]; j++) // loop till next warmer day isnt found\n if(T[j] > T[i]) \n ans[i] = j - i;\n return ans;\n }\n};\n```\n\n**Python**\n```python\nclass Solution:\n def dailyTemperatures(self, T):\n ans = [0]*len(T)\n for i in range(len(T)):\n for j in range(i+1, len(T)):\n if T[j] > T[i]:\n ans[i] = j-i\n break\n return ans\n```\n\n***Time Complexity :*** **O(N²)**, where `N` is the number of elements in the input array `T`. In the worst case, we iterate till the end of array for each index `i`. So, the total number of iterations required are `N-1 + N-2 + N-3 +...+ 1 = N(N-1)/2` which is equivalent to O(N²)\n***Space Complexity :*** **`O(1)`**, ignoring the space required by the output array\n\n---\n\n\u2714\uFE0F ***Solution - II (Decreasing Monotonic Stack)***\n\nIn the above solution, we can see that in the worst case, we are repeatedly iterating till the end of array either to find the next greater element at the very end or not finding it at all. This is redundant. We can optimize the above approach by observing that multiple elements can share a common warmer day. For eg. Consider `[4,3,2,1,5]`. In the brute-force, we would have iterated till 5th element in every case and assigned `ans[i]` as difference between the indices. However, we see that all elments share `5` as the next warmer day. \n\nThus, the pattern we see is that we **iterate forward till we find a warmer day** and **that day will be the answer for all elements before it that are cooler** (and not found a warmer day). Thus, we can **maintain a stack consisting of indices of days which haven\'t found a warmer day**. The temperature at these indices will be in decreasing order since we are only storing days that haven\'t found a warmer next day and hence it is known as decreasing monotonic stack. Whenever we find a current day `cur` which is warmer, we check elements of stack and assign them the difference of indices for all those elements which have temperature of corresponding day less than `T[cur]`.\n\n

\n\n

\n\nThus, the algorithm can be summarized as -\n\n1. Initialize an empty stack `s` and `ans` array of size `N` all initialized to 0s.\n2. Iterate over `T` from the start\n3. For each current day `cur`, check if today\'s temperature `T[cur]` is warmer than values corresponding to previous days\' indices stored in stack (`T[s.top()]`). Assign answer for all elements of stack for whom current day\'s temperature is warmer (`T[cur] > T[s.top()]`) and pop them off the stack.\n4. Push `cur` onto the stack denoting that we need to find warmer next day for `cur`.\n5. All the elements present in the stack at end don\'t have a next greater element. We don\'t have to worry about them since `ans` is already initialized to `0`. Thus, we can directly return `ans`.\n\n**\uD83D\uDCDD Dry Run**\n\nConsider `T = [73,74,75,71,69,72,76,73]`\n\nEach row\'s value in below table is the final value after completion of that step.\n\n \n \n \n \n\t\n\t\n \n \n \n \n\t\n\t\n\t\n \n \n \n \n\t\n\t\n\t\n \n \n \n \n\t\n\t\n\t\n \n \n \n \n\t\n\t\n\t\n \n \n \n \n\t\n\t\n\t\n \n \n \n \n\t\n\t\n\t\n \n \n \n \n\t\n\t\n\t\n \n \n \n \n\t\n\t\n\t\n \n

`i` / `cur`	`T[i]`	stack	ans	Description
0	73	`[0]`	`[0,0,0,0,0,0,0,0]`	Stack was empty. So, we found no element for which `T[i]` could be assigned as next warmer day. So, just pushed current day `0` to stack
1	74	`[1]`	`[1,0,0,0,0,0,0,0]`	Today\'s temperature: `74` is warmer than stack top\'s corresponding temp: `73`. So, today can be assigned as next warmer day to stack\'s top(`ans[0] = 1-0 = 1`) and then it\'s popped. Lastly push today\'s index to stack
2	75	`[2]`	`[1,1,0,0,0,0,0,0]`	Again, today\'s temperature: `75` is warmer than stack top\'s corresponding temp :`74`. So, today can be assigned as next warmer day to stack\'s top(`ans[1] = 2-1 = 1`) and then it\'s popped. Push `cur=2` to stack
3	71	`[2,3]`	`[1,1,0,0,0,0,0,0]`	Today\'s temperature: `71` is NOT warmer than stack top\'s corresponding temp :`75`. So, just push `cur=3` to stack
4	69	`[2,3,4]`	`[1,1,0,0,0,0,0,0]`	Again, today\'s temperature: `69` is NOT warmer than stack top\'s corresponding temp :`71`. So just push `cur=4` to stack
5	72	`[2,5]`	`[1,1,0,2,1,0,0,0]`	Today\'s temperature: `72` is warmer than stack top\'s corresponding temp :`69`. Assign cur as next warmer day to stack\'s top(`ans[4] = 5-4 = 1`) & pop it. Again, after popping, `72` is warmer than stack top\'s corresponding temp :`71`. Assign cur as next warmer day to stack\'s top(`ans[3] = 5-3 = 2`) & pop it. \n\tLastly, push `cur=5` to stack
6	76	`[6]`	`[1,1,4,2,1,1,0,0]`	Today\'s temperature: `76` is warmer than stack top\'s corresponding temp :`72`. Assign `ans[5] = 6-5 = 1` and pop it. Again, after popping, `72` is warmer than stack top\'s corresponding temp :`75`. Assign `ans[2] = 6-2 = 4` & pop it. Push `cur=6` to stack
7	73	`[6,7]`	`[1,1,4,2,1,1,0,0]`	Today\'s temperature: `73` is NOT warmer than stack top\'s corresponding temp :`76`. Just push `cur=6` to stack. We stop here since reached the end of array

\n\n\n**C++**\n```cpp\nclass Solution {\npublic:\n vector dailyTemperatures(vector& T) {\n stack s;\n vector ans(size(T));\n for(int cur = 0; cur < size(T); cur++) {\n while(size(s) and T[cur] > T[s.top()]) { // pop till current temp < stack\'s top\'s temp. This maintains monotonic stack\n ans[s.top()] = cur - s.top(); // cur day will be next warmer day for each element that\'s popped\n s.pop();\n }\n s.push(cur); // push onto stack to find next warmer day for cur later on\n }\n return ans;\n }\n};\n```\n\n**Python**\n```python\nclass Solution:\n def dailyTemperatures(self, T):\n ans, s = [0]*len(T), deque()\n for cur, cur_tmp in enumerate(T):\n while s and cur_tmp > T[s[-1]]:\n ans[s[-1]] = cur - s[-1]\n s.pop()\n s.append(cur)\n return ans\n```\n\n***Time Complexity :*** **O(N)**, In the worst case, we require `O(2*N) ~ O(N)` iterations.\n***Space Complexity :*** **`O(N)`**, In the worst case, we may have decreasing elements in `T` and stack will store all `N` indices in it\n\n---\n\n***\u2714\uFE0F Solution - III (Monotonic Stack - 2)***\n\nAnother way of modelling the problem in terms of monotonic stack that some may find more intuitive is by starting from the end of the array. We again maintain a monotonic stack in this case as well which is similar to above appraoch, the only change is just that we start from the end. \n\nThis will again allow us to find the next warmer element for each index just by looking through the stack. Since we are maintaining a sorted stack (increasing from top-to-bottom), we know that the first element that we find in stack for `cur`th day such that `T[s.top()] > T[cur]`, will be next warmer day required for that element.\n\n\n

\n\n

\n\nIn the above image, we start from the end and each time assign next warmer day to be top of stack element. In the 1st approach, we instead started from beginning and only assigned next warmer day/s at once once we find a warmer day than all preciding elements. Both approach should work just fine.\n\nThe algorithm can be summarized as -\n\n1. Initialize an empty stack `s` and `ans` array of size `N` all initialized to 0s.\n2. Iterate over `T` from the end.\n3. For each current day `cur`, pop values corresponding from stack that have temperature(`T[s.top()]`) lower than today\'s temperature `T[cur]`, i.e, `T[s.top()] <= T[cur]`. This popping is done because these elements are cooler than `T[cur]` and occur later on than `cur`. Thus, they will never be a potential answer for elements on the left.\n4. Now that all elements lower than `T[cur]` have been popped off, stack `s` is either empty or has some element warmer than `cur`. \n\t* If stack is empty, assign `ans[cur] = 0` because no next warmer element exists for `cur`.\n\t* Otherwise, assign `ans[cur] = s.top()-cur`, the difference between indices of next warmer element and `cur`.\n4. Then, Push `cur` onto the stack since it has potential to be next closest warmer day for remaining elements on left of `T`.\n5. Finally, return `ans`.\n\n**\uD83D\uDCDD Dry Run**\n\nAgain, consider `T = [73,74,75,71,69,72,76,73]` and we get the following steps listed in table -\n\n\n \n \n \n \n\t\n\t\n \n \n \n \n\t\n\t\n\t\n \n \n \n \n\t\n\t\n\t\n \n \n \n \n\t\n\t\n\t\n \n \n \n \n\t\n\t\n\t\n \n \n \n \n\t\n\t\n\t\n \n \n \n \n\t\n\t\n\t\n \n \n \n \n\t\n\t\n\t\n \n \n \n \n\t\n\t\n\t\n \n

`i` / `cur`	`T[i]`	stack	ans	Description
7	73	`[7]`	`[0,0,0,0,0,0,0,0]`	Stack was empty. So, we found no next warmer element for `T[i]`. Assign `ans[7] = 0`and push current day `7` to stack
6	76	`[6]`	`[0,0,0,0,0,0,0,0]`	Stack\'s top\'s temp: `73` is less than today\'s temperature:`76`. So, pop it since it can\'t ever be next warmer element for any day. Again, stack is empty and so there\'s not next warmer element for today. Assign `ans[6] = 0`and push current day `6` to stack
5	72	`[6,5]`	`[0,0,0,0,0,1,0,0]`	Stack\'s top\'s temp: `76` is warmer than today\'s temperature:`72`. So assign `ans[5] = 6-5 = 1`. Then, push current day `5` to stack
4	69	`[6,5,4]`	`[0,0,0,0,1,1,0,0]`	Stack\'s top\'s temp: `72` is warmer than today\'s temperature:`69`. So assign `ans[4] = 6-5 = 1`.and push current day `4` to stack
3	71	`[6,5,3]`	`[0,0,0,2,1,1,0,0]`	Stack\'s top\'s temp: `69` is less than today\'s temperature:`71`. So pop it. Now, stack\'s top has greater temp so we break out of loop and assign `ans[3] = 5-3 = 2`.and push current day `3` to stack
2	75	`[6,2]`	`[0,0,4,2,1,1,0,0]`	Stack\'s top\'s temp: `71` is less than today\'s temperature:`75`. So pop it. Again, stack\'s top temp: `72` is less than 75. So, pop it again. Now, stack\'s top temp is greater so we break out of loop and assign `ans[2] = 6-2 = 4`.and push current day `2` to stack
1	74	`[6,2,1]`	`[0,1,4,2,1,1,0,0]`	Stack\'s top\'s temp: `75` is warmer than today\'s temperature:`74`. So assign `ans[1] = 2-1 = 1`.and push current day `1` to stack
0	73	`[6,2,1,0]`	`[1,1,4,2,1,1,0,0]`	Stack\'s top\'s temp: `74` is warmer than today\'s temperature:`73`. So assign `ans[0] = 1-0 = 1`.and push current day `0` to stack

\n\n\n**C++**\n```cpp\nclass Solution {\npublic:\n vector dailyTemperatures(vector& T) {\n stack s;\n vector ans(size(T));\n for(int cur = size(T)-1; cur >= 0; cur--) {\n\t\t// pop till current temp > stack top\'s temp. All popped element can never be next warmer day for any other elements\n while(size(s) and T[s.top()] <= T[cur]) s.pop(); \n ans[cur] = s.empty() ? 0 : s.top() - cur; // no warmer element exists if stack empty. Otherwise, assign distance between stack\'s top and cur day\n s.push(cur); // push onto stack as it can potentially be next warmer day for rest elements\n }\n return ans;\n }\n};\n```\n\n**Python**\n```python\nclass Solution:\n def dailyTemperatures(self, T):\n ans, s = [0]*len(T), deque()\n for cur in range(len(T)-1,-1,-1):\n while s and T[s[-1]] <= T[cur]:\n s.pop()\n ans[cur] = s[-1] - cur if s else 0\n s.append(cur)\n return ans\n```\n\n***Time Complexity :*** **O(N)**, same as above\n***Space Complexity :*** **`O(N)`**, In worst case, we may have increasing elements in `T` and stack will store all `N` indices in it.\n\n---\n\n***\u2714\uFE0F Solution - IV (Space Optimized Version)***\n\nIn the above appraoch, we maintained an explicit stack to track indices of all elements that can potentially be next warmer day for some remainings days. Now, instead of maintaining explicit stack, we can observe that `ans` itself to find the next warmer day. \n\n**How?** We know that `ans[i]` holds number of days after `i` that a warmer day occurs. Then, for some other day `cur` such that `cur < i`, we can start at `next = cur+1` and then use `ans` array to traverse till we find next warmer day. Each time we compare temperature at `next` and `cur` day and stop only when we find next day which has higher temperature. **Now, this the main part**. Instead of iterating by 1-by-1 as in brute-force, **we use `ans` to make jumps to next potential warmer day**, just as we did in stack-based solution. This helps us keep the solution to `O(N)` while also avoiding the use of extra stack.\n\n**C++**\n```cpp\nclass Solution {\npublic:\n vector dailyTemperatures(vector& T) {\n vector ans(size(T));\n for(int n = size(T), cur = n-2; cur >= 0; cur--) {\n int next = cur + 1; // start at next day & iterate till you find next warmer day (NWD)\n while(next < n && T[next] <= T[cur]) // jump till you reach NWD\n next += ans[next] ? ans[next] : n; // ?: operator just to make sure that if we reach ans[next], we know NWD doesnt exist, so jump direct to end\n if(next < n) ans[cur] = next-cur; // if next > n, NWD doesnt exist. Otherwise, assign distance to NWD\n }\n return ans;\n }\n};\n```\n\n**Python**\n```python\nclass Solution:\n def dailyTemperatures(self, T):\n ans, n = [0]*len(T), len(T)\n for cur in range(n-2,-1,-1):\n nxt = cur+1\n while nxt < n and T[nxt] <= T[cur]:\n nxt += ans[nxt] if ans[nxt] else n\n ans[cur] = nxt-cur if nxt < n else 0\n return ans\n```\n\n\n***Time Complexity :*** **O(N)**, just as in stack based solution, we are jumping to next potential warmer day instead of iterating 1 after another. This ensures, we perform a max of `O(2N) \u2248 O(N)` iterations\n***Space Complexity :*** **`O(1)`**, ignoring the output space we are only using constant extra space.\n\n---\n---\n\n\uD83D\uDCBBIf there are any suggestions / questions / mistakes in my post, comment below \uD83D\uDC47 \n\n---\n---

Daily Temperatures

Problem Description

Problem Description

Answer Panel