The O(n) Club: Daily Temperatures: When Will It Be Warmer? (Stack, Don’t Sweat)

The O(n) Club: Daily Temperatures—When Will It Be Warmer? (Stack, Don’t Sweat)

⚡ TL;DR

Got a list of temperatures? For each day, you want to know how many days till it finally gets warmer. You could brute force with two loops—if you’re free all weekend and your laptop wants to retire early. Check this out:

// Slow and sad ☹️
int[] dailyTemperatures(int[] temps) {
  int n = temps.length;
  int[] res = new int[n];
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (temps[j] > temps[i]) {
        res[i] = j - i;
        break;
      }
    }
  }
  return res;
}

If that made your fan turn on, there’s a better way. Enter the monotonic stack: elegant, O(n), and guaranteed to impress your favorite interviewer.

🧠 How Devs Usually Mess This Up

Most eager coders fire up nested loops—simple, but it goes down like a Jenga tower at scale. Some folks misuse stacks and push temperatures—not indices—so they trip on index math later. And let’s not forget those who forget zeros for “never gets warmer” days (you’ll spot them by their haunted stares after facing test case #2435).

🔍 What’s Actually Going On

Think of each day as a hopeful Java dev at standup. The stack holds indices of still-waiting optimists. Each time a new, hotter temp arrives, it’s like a company-wide coffee delivery—those waiting get their wish (and a result value). The stack is monotonic decreasing: when a higher temp arrives, we celebrate and update everyone’s calendar.

🛠️ PseudoCode

• Initialize result array res with zeros.
  (Zeros mean “sorry, you’ll always be cold!”)
• Start an empty stack for indices.
  Stack<Integer> stack = new Stack<>();
• Loop through each day (curr):
  • While stack isn’t empty and today’s temp is hotter than temp[stack.peek()]:
    • Pop prev index off stack,
    • Set res[prev] = curr - prev
  • Push curr onto stack.
• After the loop, res has all answers. Indices still in stack? They’ll be cold forever (already zero!).

💻 The Code

public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] res = new int[n]; // Zeros by default
    java.util.Stack<Integer> stack = new java.util.Stack<>();
    for (int curr = 0; curr < n; curr++) {
        while (!stack.isEmpty() && temperatures[curr] > temperatures[stack.peek()]) {
            int prev = stack.pop();
            res[prev] = curr - prev;
        }
        stack.push(curr);
    }
    return res;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Zero-initialization is your friend: Unmatched cold days? They stay zero. Don’t manually overwrite.
• Don’t push temps to the stack: Only indices let you calculate day differences. Learn from other people’s StackOverflow posts.
• Worried about time/space? No need! Each index enters/exits the stack just once—O(n) all the way.
• Don’t get cute with recursion: It’ll just confuse you (and your interviewer).

🧠 Interviewer Brain-Tattoo

Store indices, not temperatures—unless you want your interviews to heat up for all the wrong reasons. Monotonic stack: the hottest club in algorithm town!

“Why wait for a hotter day the slow way, when you can just stack up the wins?”