Full lesson preview

Find the next greater element for each index

For each element in an array, find the next element to its right that is greater; return -1 if none exists.

Python practice25 minArrays – Fundamentals & PatternsAdvancedLast updated March 25, 2026

Problem statement

Given an array nums, for each element nums[i] find the first element to its right that is greater than nums[i]. If no such element exists, record -1 for that position. Return a list of the same length where each position contains the next greater element or -1. You should implement an O(n) solution using a stack that keeps indices of elements for which the next greater hasn't been found yet.

Task

Use a monotonic stack to compute next greater elements in O(n) time and O(n) space.

Examples

Simple example

Input

nums = [4, 5, 2, 25]

Output

[5, 25, 25, -1]

4 -> 5, 5 -> 25, 2 -> 25, 25 -> -1 since no greater element to its right.

Input format

One argument: a list of integers nums. Example: next_greater_elements([2,1,2,4])

Output format

List of integers where each position is the next greater element to the right, or -1.

Constraints

0 <= len(nums) <= 10^5. -10^9 <= nums[i] <= 10^9. Aim for O(n) time and O(n) additional space.

Samples

Sample 1

Input

nums = [2, 2, 2]

Output

[-1, -1, -1]

No element has a strictly greater element to its right.