503. Next Greater Element II

503

MediumMonotonic Stack and Monotonic QueueMonotonic decreasing stackNext greater element (circular)

Next Greater Element II

Given a circular integer array nums (the element after the last wraps around to the first), return an array where each position holds the next greater number when searching forward circularly. If no greater number exists, use -1.

Open official problem prompt ↗

In plain English

For each element, find the first strictly larger value that appears when scanning forward and wrapping around the end of the array.

Picture it like this

Imagine people standing in a circle by height, each looking clockwise for the first person taller than them. A short person keeps looking until someone taller appears; that taller person 'answers' everyone shorter who was still searching.

Example

Input: nums = [1, 2, 1]
Output: [2, -1, 2]
Why: For nums[0]=1 the next greater is 2; for nums[1]=2 nothing larger exists; for nums[2]=1 the search wraps around and finds 2.

Constraints

1 <= nums.length <= 10^4-10^9 <= nums[i] <= 10^9

Pattern lesson

See the pattern, then code

Next greater element (circular)

↗

Monotonic Stack and Monotonic Queue

Next greater or smaller value, nearest boundary, histogram, or window extremum.. A monotonic decreasing stack of indices holds elements still waiting for their answer; the current value resolves every smaller value beneath it. Iterating 2n times (using i % n) simulates the wrap-around without physically doubling the array.

New words, made simpleKnow these before the algorithm

Next greater element: The first value to the right (here, circularly) that is strictly larger than the current one.
Monotonic decreasing stack: A stack whose stored values never increase from bottom to top; a larger incoming value pops everything smaller.
Circular traversal: Treating index n as index 0 again, done here by iterating 2n times and using i % n.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Brute force per index

Quadratic; too slow when n reaches 10^4 across many test cases.

For each index, walk forward up to n-1 steps (mod n) until a larger value is found.

Time O(n^2)Space O(1)

Best choiceMonotonic stack over a doubled sweep

Each index is pushed and popped at most once, giving linear time while handling the circular case.

Keep indices of unresolved elements on a decreasing stack and sweep 2n positions so wrap-around answers are captured.

Time O(n)Space O(n)

The rule we keep true

Invariant

The stack always holds indices of elements not yet given an answer, in strictly decreasing order of their values from bottom to top.

Why this is correct

Reasoning

When cur exceeds the value at the stack top, cur is by construction the first larger value encountered to that index's right, so it is exactly the next greater element. Sweeping twice guarantees wrap-around candidates are seen; guarding the push with i < n prevents recording an index's answer more than once. Anything left on the stack after the sweep never found a larger value and keeps its -1.

The algorithm in three movesSay these aloud before coding

1Initialize res filled with -1 and an empty index stack

i=1 cur=2: pop idx0 -> res[0]=2

2Loop i from 0 to 2n-1, reading cur = nums[i % n]

stack=[1] (value 2, unresolved)

3While the stack top's value is less than cur, pop it and set its result to cur

i=3 (wrap) cur=1: no pop; res[1] stays -1, res[2]=2

4Only push the index during the first pass (i < n) so answers are recorded once

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readcur = nums[0] = 1

2 · AskAny smaller unresolved value to pop?

3 · Update statestack empty

4 · ResultPush index 0. stack=[0]

Key takeaway

The value 2 at index 1 resolves index 0; index 1 itself never finds anything larger even after wrapping.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-5Set up results and stack
res defaults to -1 so any index left unresolved is already correct; the stack holds unresolved indices.
2
Lines 6-7Sweep twice with modular indexing
Iterating 2n times and reading nums[i % n] simulates the circular array without allocating a doubled copy.
3
Lines 8-9Resolve smaller values
Every stacked index whose value is below cur gets cur as its next greater element, then is popped.
4
Lines 10-11Push only in the first pass
Guarding with i < n ensures each index enters the stack once, so its answer is written at most once.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Single element returns [-1]
All equal elements return all -1 because the comparison is strict
Strictly decreasing array: every element except the max wraps around to find the max
Negative values mixed with positives are handled naturally by the comparison

Common beginner mistakes

Using <= instead of < would treat equal values as 'greater' and give wrong answers
Forgetting the i < n guard re-pushes indices and can overwrite correct answers
Only iterating n times misses wrap-around answers
Storing values instead of indices makes it impossible to write into res

Check your understanding

Why iterate exactly 2n times rather than 3n or more?

Next Greater Element II

Next Greater Element II

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Monotonic Stack and Monotonic Queue