## [Programming Problem] Daily Temperatures

Mar 14

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

If you find a decreasing sequence keep moving forward until you find the number that breaks the sequence. Once you find that, move backward to find temperatures lower than that one. We could use a stack for this.

- Keep adding temperatures to a stack.
- If current temperature is less than or equal to the last element, add this temperature to the stack.
- If you find the current temperature is more than the last element on the stack you’ve found the next highest temperature for it (and possibly some temperatures before that). Keep doing this while the topmost element on the stack is less than the current temperature.

Basically when you find a decreasing sequence, just keep adding it to the stack. When that sequence breaks (meaning you find an element higher than the previous one), keep pop-ing elements from the stack to find temperatures that are lesser than the current temperature. We store indexes (and not actual temperatures) on the stack, so that we can calculate the days elapsed as we go.

Time and space complexity for this would be O(N)

/** * @param {number[]} T * @return {number[]} */ var dailyTemperatures = function(T) { if ( T.length === 0 ) return []; let ret = []; let arr = [ 0 ]; T.forEach(function(curr, i) { if ( i === 0 ) return; while ( arr.length > 0 && T[arr[arr.length-1]] < curr ) { let lastElement = arr.pop(); ret[lastElement] = i - lastElement; } arr.push(i); }); if ( arr.length > 0 ) { arr.forEach(function(curr) { ret[curr] = 0; }); } return ret; }; |

## Recent Comments