Next Larger Element

Given an array arr, for each element find the next greater element to its right — the first element further right that is strictly greater. If there is none, use -1.

Return an array of these next-greater values, one per position.

Hints

· Stuck? Reveal one nudge at a time.

Scanning right from each element is O(n^2) — can you reuse comparisons?

Sweep right to left, keeping a stack that stays decreasing.

Pop everything <= the current element; the remaining top is its next greater.

Common doubts

The next-greater element lies to the right, so processing right first means the relevant candidates are already on the stack when you reach index i.

Once arr[i] sits to their left, a smaller-or-equal stacked value can never be the next-greater of anything further left — arr[i] blocks it. So it's useless.

Each element is pushed once and popped at most once over the whole run, so the total pop work is O(n) — the inner loop is amortized O(1).

Interview follow-ups

· What an interviewer asks next.

Keep an increasing stack and pop elements >= the current one; the same template, flipped.

Iterate the indices twice (mod n) so elements can wrap around to find a greater element earlier in the array — that's Next Greater Element II.

Fun facts

The monotonic stack is the workhorse behind next/previous greater/smaller — and, through those, histogram and subarray-domination problems.
The amortized 'each element pops once' argument is the same accounting used for the two-stack queue.

Asked at

AmazonFlipkartMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: arr = [1, 3, 2, 4]
Output: [3, 4, 4, -1]
Next greater to the right of 1 is 3; of 3 is 4; of 2 is 4; of 4 there is none (-1).

Example 2

Input: arr = [6, 8, 0, 1, 3]
Output: [8, -1, 1, 3, -1]
8 has no greater element to its right, and neither does the last 3.

Constraints

- 1 <= arr.length <= 10^6 - 1 <= arr[i] <= 10^9

For each element you want the first strictly-greater element to its right. Scanning rightward every time is O(n²) and redoes work. A monotonic decreasing stack, swept right to left, reuses those comparisons: it holds exactly the elements that could still be some earlier element's answer, so the answer is always sitting right on top.

Prerequisites

Before you start

· Concepts used directly in the solution.

Monotonic stack. A stack kept in decreasing order by popping smaller-or-equal elements before pushing.

Amortized O(n). Each element is pushed once and popped at most once across the whole sweep.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Definitions

“Strictly greater or greater-or-equal?”

Strictly greater — an equal value is not a valid next-greater.

“What if nothing to the right is greater?”

The answer for that position is -1.

The ideal opening — say it like this

For each element I need the first strictly greater element to its right.

I sweep right to left with a stack that stays decreasing, popping anything at most as large as the current element.

Whatever remains on top is the next greater element; then I push the current value.

Understand the problem

Worked example — arr = [1, 3, 2, 4]

i=3 (4): stack empty -> res[3]=-1; push 4 -> [4]
i=2 (2): top 4 > 2   -> res[2]=4;  push 2 -> [4,2]
i=1 (3): pop 2 (<=3) -> top 4 > 3 -> res[1]=4; push 3 -> [4,3]
i=0 (1): top 3 > 1   -> res[0]=3;  push 1 -> [4,3,1]
answer: [3, 4, 4, -1]

Key observations

1Aha

Smaller-or-equal elements are useless once passed

If arr[i] is at least as large as a stacked value, that value can never be the next-greater of anything to the left of i — arr[i] blocks it. So pop it.

2Aha

The stack stays decreasing

After popping the <= arr[i] elements and pushing arr[i], the stack remains decreasing bottom-to-top, so its top is always the nearest greater element to the right.

3Aha

Each element enters and leaves once

A value is pushed exactly once and popped at most once, making the total work O(n) despite the inner while-loop.

Brute force vs optimal

	Scan right each time	Monotonic stack
Idea	For each i, scan right for the first greater	Sweep right-to-left, keep a decreasing stack
Time	O(n^2)	O(n)
Space	O(1)	O(n)

The brute rescans overlapping suffixes; the stack keeps only the candidates that can still be an answer. Full code is in the Approaches selector below.

Summary

Key takeaway

Sweep right to left with a decreasing stack. For each element, pop everything <= it; the remaining top (or -1) is its next-greater element; then push it. Amortized O(n).

res = [-1] * n; stack = []
for i from n-1 down to 0:
    while stack and stack.top <= arr[i]: pop
    res[i] = stack.top if stack else -1
    push arr[i]
return res