How do you find the next greater element for every item in an array?
Use a monotonic stack of indices. Walk left to right; while the current value is greater than the value at the stack top, that top has found its next greater element. Then push the current index.
Explain it simply
For each person in a queue, you want the first taller person standing to their right. A naive check for every person is O(n squared).
Keep a stack of people still waiting for someone taller. When a new person arrives, everyone on the stack who is shorter than them has just found their answer, so pop them and record this person. Then the new person joins the waiting stack. The stack always stays in decreasing order of height, hence "monotonic".
Example
function nextGreater(nums) {
const result = new Array(nums.length).fill(-1);
const stack = []; // indices waiting for a greater value
for (let i = 0; i < nums.length; i++) {
while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
result[stack.pop()] = nums[i];
}
stack.push(i);
}
return result;
}
console.log(nextGreater([2, 1, 2, 4, 3])); // Output: [4,2,4,-1,-1]Complexity
Time O(n), space O(n).
What to say in the interview
"I keep a stack of indices whose next greater value is still unknown. When I meet a bigger value, I pop smaller ones and fill in their answer. Each index is pushed and popped once, so it is O(n) time and O(n) space. The same pattern solves daily temperatures and stock span."
Common mistakes
- Pushing values instead of indices, so you cannot write the result at the right position.
- Using nested loops and calling it optimal.