How to Find the Next Greater Element for Each List Item in Python
Use a monotonic stack to find the next greater element to the right for every item in a list, in O(n) time.
Python code
16 linesdef next_greater_element(nums):
result = [-1] * len(nums)
stack = []
for i in range(len(nums) - 1, -1, -1):
while stack and stack[-1] <= nums[i]:
stack.pop()
result[i] = stack[-1] if stack else -1
stack.append(nums[i])
return result
if __name__ == "__main__":
sample = [4, 5, 2, 25, 10]
print(next_greater_element(sample))Output
[5, 25, 25, -1, -1]How it works
The function iterates from right to left, maintaining a stack that holds potential next greater elements for the current index. While the top of the stack is less than or equal to the current value, it's popped because it can't be the answer for any earlier element. The top after popping is the next greater element (or -1 if the stack is empty). The current value is then pushed to act as a candidate for earlier indices. This ensures each element is pushed and popped once, yielding O(n) time.
Common mistakes
- Forgetting that equal elements don't count as greater, so you need `<=` in the while condition.
- Returning the element itself when no greater element exists instead of -1.
- Mixing up the direction — scanning left to right requires a different approach with an output array.
Variations
- Find the next greater element to the left by scanning left to right with the same stack logic.
- Use a dictionary to map each element to its next greater element for more complex lookups.
Real-world use cases
- Computing spans in stock prices: for each day, how far back the price stayed lower — a standard financial indicator.
- Solving the 'daily temperatures' problem in LeetCode by finding the number of days until a warmer temperature.
- Parsing nested structures like parentheses matching where you need the next matching delimiter position.
Sponsored
More from Algorithms & data structures
- Binary Search for Ship Capacity in Python medium
- Binary Search on Answer in Python: Koko Eating Bananas medium
- Bucket Numbers into Histogram Bin Counts in Python easy
- Container With Most Water: Two-Pointer Solution in Python medium
- Count Smaller Elements to the Right in Python easy
- Depth First Search Traversal Order in Python easy
Keep learning
Related tutorials and quizzes for this topic.