Why does this monotonic stack return the wrong next greater values for duplicate elements?

programming web dev
1

I’m implementing next greater element with a monotonic stack, but duplicates seem to break it. For input [2, 2, 3] I expect [3, 3, -1], yet I get [-1, 3, -1]. I think my map is overwriting something, but I’m not sure what the right fix is without losing O(n).

function nextGreater(nums) {
  const st = [], ans = new Map();
  for (const x of nums) {
    while (st.length && st[st.length - 1] < x) {
      ans.set(st.pop(), x);
    }
    st.push(x);
  }
  return nums.map(x => ans.get(x) ?? -1);
}
console.log(nextGreater([2, 2, 3]));

Should I be storing indices instead of values here?

Ellen

2

Yes, store indices, because Map(value -> nextGreater) collapses both 2s into one bucket and duplicates are where the gremlin lives.

Arthur