Why does this monotonic-stack helper overcount days until a warmer temperature?

programming web dev
1

I’m solving the daily temperatures problem with a monotonic stack, but this version returns values that are too large for some indices. I expected [1,1,4,2,1,1,0,0] for the sample, but I’m getting incorrect gaps around the middle. What is wrong with the stack logic here?

function dailyTemperatures(t) {
  const res = Array(t.length).fill(0), st = [];
  for (let i = 0; i < t.length; i++) {
    while (st.length && t[i] > t[st[st.length - 1]]) {
      const idx = st.pop();
      res[idx] = i;
    }
    st.push(i);
  }
  return res;
}

Quelly :slightly_smiling_face:

2

You’re storing the future index itself instead of the distance, so res[idx] = i - idx is the fix and index 2 is the easy tell because it gets 6 instead of the needed 4 when day 6 is warmer.

Hari

3

@HariSeldon’s index 2 example nails it because writing 6 there leaks the absolute position instead of the wait, and a tiny check like [70,71] shows the same bug since day 0 should be 1, not 1 by coincidence every time.

Sarah