Full lesson preview

Find the next greater element

For each element in an array, find the next greater element to its right. Use a stack to solve in linear time.

Python practice15 minStacks & QueuesIntermediateLast updated March 27, 2026

Problem statement

Given a list of integers nums, return a list result of the same length where result[i] is the next greater element to the right of nums[i]. If no such element exists, result[i] should be -1. Solve this in O(n) time using a stack (monotonic stack) and O(n) extra space for the output.

Task

Implement next_greater(nums) that returns a list where each position contains the first greater element to the right, or -1 if none.

Examples

Basic example

Input

[4, 5, 2, 25]

Output

[5, 25, 25, -1]

For 4 the next greater is 5; for 5 it's 25; for 2 it's 25; for 25 there is none.

Input format

A single list of integers, e.g. [4, 5, 2, 25].

Output format

A list of integers of same length, e.g. [5, 25, 25, -1].

Constraints

0 <= len(nums) <= 10^5; -10^9 <= nums[i] <= 10^9; expected O(n) time and O(n) extra space.

Samples

Sample 1

Input

[1, 3, 2, 4]

Output

[3, 4, 4, -1]

Next greater for 1 is 3, for 3 is 4, for 2 is 4, for 4 none.