core practice · coding problem
Next greater element
Implement nextGreater(nums) returning an array where result[i] is the next element to the right strictly greater than nums[i], or -1 if none. Must be O(n) — each index pushed and popped at most once.
The mechanism
Keep the stack monotonic and every element enters and leaves exactly once, so a shape that looks like a nested loop is linear. The moment you pop is the moment you have learned something: the element being popped has just found its next greater (or smaller) neighbour, which is why the answer is written on pop rather than on push.
Expected evidence
nextGreater([2,1,2,4,3]) -> [4,2,4,-1,-1]
Try this drill in the practice workspace →
Hints when you need them
- Keep a stack of INDICES whose answer is still unknown, with decreasing values.
- When the current element is greater than the value at the stack top, you have just found that index's answer — pop and record.
Watch for these mistakes
- Storing values when you need indices — most answers require the distance, not the element
- Choosing the wrong strictness, so equal elements are handled inconsistently at the boundary
- Forgetting the leftovers: whatever is still on the stack at the end has no next greater element
- Assuming O(n^2) because of the inner while loop, when the amortised bound is linear