Free Stacks and queues lessonsStacks and queues · Stage 2 · Monotonic stack · Step 1

The next bigger value on the right

For every item, find the first value to its right that is bigger, by keeping a stack of items still waiting for something bigger. About 14 minutes.

Items waiting for an answer

For each number, you want the first bigger number to its right. Think of every number as waiting for that answer. When a new number arrives, it answers every waiting number that is smaller than it.

Keep the waiting numbers on a stack, as positions. The waiting numbers on the stack always go from biggest at the bottom to smallest on top, so the ones that a new value beats are exactly the ones on top.

New value: answers every smaller item on top of the stack.

Then push it, since it now waits for its own answer.

In code

for i, x in enumerate(nums):
    while stack and nums[stack[-1]] < x:
        res[stack.pop()] = x
    stack.append(i)

Next bigger on the right for 2, 1, 2, 4, 3.

2 arrives. Nothing is waiting, so push it. Waiting: 2.

Move 1 of 5

Items that never get answered

When the scan ends, the positions still on the stack never found a bigger value to their right. Their answer stays at minus one, so start the answer list filled with minus one and write to it only when an item is answered.

Each position goes onto the stack once and comes off at most once. That is why the whole pass costs about two steps per item, no matter how many items are popped by one value.

Start with minus one: in every answer slot.

Compare strictly: an equal value is not bigger.

In code

res = [-1] * len(nums)
stack = []

Quick check

A value arrives that equals the number on top of the stack. What happens?

AThe value is pushed, since equal is not bigger
BThe top is popped and answered
CThe value is ignored

Show the answer

The value is pushed, since equal is not bigger. Only a strictly bigger value answers a waiting item.

Your problem

Next greater element

Given an array nums, return an array answer of the same length where answer[i] is the first value to the right of position i that is strictly greater than nums[i], or -1 if there is none.

Example

nums = [2, 1, 2, 4, 3] → [4, 2, 4, -1, -1]

1 ≤ length of nums ≤ 100,000 · -1,000,000,000 ≤ nums[i] ≤ 1,000,000,000

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.