Daily Temperatures

Problem (restated)

Given daily temperatures, return an array answer where answer[i] is the number of days you wait after day i for a warmer temperature. If none, answer[i]=0.

Intuition

Next greater element → monotonic decreasing stack of indices. When a warmer day appears, pop and record distance.

Approaches

export function dailyTemperatures(temperatures: number[]): number[] {
  const n = temperatures.length;
  const ans = new Array<number>(n).fill(0);
  const stack: number[] = [];
  for (let i = 0; i < n; i++) {
    while (stack.length && temperatures[i]! > temperatures[stack[stack.length - 1]!]!) {
      const j = stack.pop()!;
      ans[j] = i - j;
    }
    stack.push(i);
  }
  return ans;
}

export function dailyTemperatures(temperatures: number[]): number[] {
  const n = temperatures.length;
  const ans = new Array<number>(n).fill(0);
  const stack: number[] = [];
  for (let i = 0; i < n; i++) {
    while (stack.length && temperatures[i]! > temperatures[stack[stack.length - 1]!]!) {
      const j = stack.pop()!;
      ans[j] = i - j;
    }
    stack.push(i);
  }
  return ans;
}

Template connection

Monotonic stack next-greater template.

Reflection

• Which pattern gave this away within 90 seconds?
• What changed from the standard template?
• What would break the current solution?