easy +10 pts

Next Greater Element

For each element, find the first greater value to its right using an efficient stack approach.

Share
stack arrays monotonic stack
Write a function `next_greater_element(nums)` that takes a list of integers `nums` and returns a list of the same length where each element at index `i` is the first integer to the right of `nums[i]` that is strictly greater than `nums[i]`. If no such greater element exists, put `-1` at that position. The input list may be empty; for an empty list, return an empty list.

Constraints

`0 <= len(nums) <= 10^5`. Each element: `-10^9 <= nums[i] <= 10^9`. Expected time complexity O(n), where n is the length of the list. Do not use a naive O(n^2) double loop.

Example

>>> next_greater_element([4, 5, 2, 25])
[5, 25, 25, -1]
>>> next_greater_element([13, 7, 6, 12])
[-1, 12, 12, -1]
>>> next_greater_element([1, 2, 3, 4])
[2, 3, 4, -1]
>>> next_greater_element([])
[]
10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Process the array from right to left to know what lies ahead.
Maintain a stack of indices (or values) that are strictly decreasing from bottom to top.
When you see a new element, pop from the stack until you find a greater value or the stack empties.
The top of the stack after popping is the next greater element for the current position.
Python 3
All tests passed!
Test Results
Press Ctrl+Enter or click Run Tests to execute your code.