# Daily Temperatures

public class Solution {
public int[] DailyTemperatures(int[] temperatures) {
int[] temp = new int[temperatures.Length];
for(int i = 0; i < temperatures.Length; i++){
int tmp = 0;
bool isChecked = false;
for(int j = i + 1; j < temperatures.Length && !isChecked; j++){
tmp++;
if(temperatures[j] > temperatures[i]){
temp[i] = tmp;
isChecked = true;
}
}
}
return temp;
}
}

• The idea of my solution was the same as in the stack approach but I implemented it through a dictionary/HashMap with items of the form {temp : date}. How much could it affect the complexity of the algorithm?

• My solution offers the same complexity, but relying on `O(N)` storage (only `T`, the list containing the result); it is based on Dynamic Programming.

The base case is the last temperature, for which `T[N] = 0`. For every subsequent temperature `n = N-1, N-2, ..., 0`, we either have

``````temperature[n] < temperature[n + 1]
``````

in which case `T[n] = 1` and we can proceed to the next value. Otherwise, we have

``````temperature[n] >= temperature[n + 1]
``````

in which case we find the next warmer day as follows:

If `T[n + 1] = 0`, we know that `T[n] = 0` and can proceed to the next case. This is because `temperature[n]` is already warmer than `temperature[n + 1]`, and `T[n + 1] = 0` tells us that there are no future days warmer than `temperature[n + 1]`.

If, on the other hand, `T[n + 1] > 0`, we skip to `T[n + 1 + T[n + 1]]` and repeat the rationale.

The inner loop will traverse at most as many times as there are temperatures, so it is bounded above by `M` (the number of possible temperatures), therefore the complexity of `N M` is `O(N)`.

``````  vector<int> dailyTemperatures(vector<int>& temperatures) {
const auto N = temperatures.size();

if (N == 1) return {0};

vector<int> T(N, 0);

for (auto k = N - 2; k < N; --k) {
if (temperatures[k] < temperatures[k + 1]) {
T[k] = 1;
continue;
}

if (T[k + 1] == 0) continue;

for (auto j = k + 1 + T[k + 1]; j < N; j += T[j]) {
if (temperatures[k] < temperatures[j]) {
T[k] = j - k;
break;
}
if (T[j] == 0) break;
}
}

return T;
}
``````

• an O(n*2) algorithm passes the tests (ie, brute force check), so maybe that should be documented or ruled out in the testing.

• this is super brute force and passes but no ideal obviously....

``````   public int[] dailyTemperatures(int[] temperatures) {
int[] ret = new int[temperatures.length];

for (int i = 0; i < temperatures.length-1; i++){
int x = temperatures[i];
ret[i] = 0;
for (int j = i+1; j < temperatures.length; j++){
int y = temperatures[j];
if (y - x > 0){
ret[i] = j - i;
break;
}
}
}
return ret;
``````

• Should the size of the stack represent the longest run of decreasing temperature?

• Don't see why we do it backwards. Unnecessary IMHO.

``````int[] result = new int[temperatures.length];
Stack<Integer> stack = new Stack<>(); // Make it a stack of indices.
for (int i = 0; i < temperatures.length; i++) {
while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
int index = stack.pop();
result[index] = i - index;
}
stack.push(i);
}
return result;
``````

• The output of "Next Array" method is [0,0,0,0,0,0,0], is there anyone get the same result as mine?

Used slicing

inputList = [73, 74, 75, 71, 69, 72, 76, 73]
resultList = [0]*len(inputList)

index = 0
for num in inputList:
innerIndex = index + 1
for max in inputList[innerIndex : len(inputList)]:
if max >= num:
resultList[index] = innerIndex - index
break
innerIndex += 1
index += 1

print(resultList)

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