Next Greater Element

Medium

Decreasing stack, popped means answered

Problem

For each element, find the next element to its right that is greater, or -1 if none.

In simple words

Use a stack of indices waiting for a bigger value; when one arrives, it answers all smaller ones behind it.

The idea

Sweep the array holding a stack of values still waiting for a bigger neighbour. When the current element exceeds the stack top, that top's answer is this element — pop and record it. Whatever is left unanswered gets -1.

The trick

Each element is pushed and popped once, so the sweep is O(n).
Anything remaining on the stack has no greater element to its right.
Sweeping right to left with a different stack condition works equally well.

←→stepspaceplay

1/6

Brute force

timeO(n²)spaceO(1)

Scan right each time.

1// for each element, scan right for the next bigger2for (let i = 0; i < n; i++) {3  res[i] = -1;4  for (let j = i + 1; j < n; j++)5    if (nums[j] > nums[i]) { res[i] = nums[j]; break; }6}

Input

array: [4, 5, 2, 25]

Memory

i: —
j: —

Output

done: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: nums = [4, 5, 2, 25]
Output:: [5, 25, 25, -1]
Explanation:: For 4→5, 5→25, 2→25, 25→none(-1).

Example 2

Input:: nums = [13, 7, 6, 12]
Output:: [-1, 12, 12, -1]
Explanation:: 7 and 6 both look ahead to 12.

Example 3

Input:: nums = [1, 2, 3]
Output:: [2, 3, -1]
Explanation:: Each looks to the next bigger; last is -1.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.