Next Greater Element II

Given a circular integer array nums (the element after the last is the first), return the next greater number for every element — the first strictly greater value encountered when moving forward and wrapping around. If none exists, use -1.

Hints

· Stuck? Reveal one nudge at a time.

It's next-greater-element, but the array wraps around.

Iterate 2n indices using i % n so elements can find greater values that wrap.

Keep an index stack decreasing by value; push only during the first pass.

Common doubts

A single pass can't let an early element find a greater value that appears earlier in the array. A second pass over the same indices (via i % n) covers the wrap-around.

The elements are already on the stack after the first pass. The second pass exists only to resolve them, not to add duplicates.

You need to write the answer at the correct position when an element is resolved, so the stack holds indices.

Interview follow-ups

· What an interviewer asks next.

Pop with <= instead of <, so equal values also resolve pending indices.

Mirror it: iterate 2n from the right (or reverse the roles), keeping the same decreasing index stack.

Fun facts

The 'process 2n with modulo' trick turns any linear array-scan into a circular one — used for circular subarray sums too.
This is the same monotonic stack as the linear version; only the loop bound and indexing change.

Asked at

AmazonGoogleMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: nums = [1,2,1]
Output: [2,-1,2]
The last 1 wraps around to find 2; the 2 has no greater element.

Example 2

Input: nums = [1,2,3,4,3]
Output: [2,3,4,-1,4]
The last 3 wraps around to find 4; the 4 finds nothing greater.

Constraints

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

It's the next-greater-element problem on a circular array. The monotonic-stack template still applies — you just walk the indices twice (using i % n) so an element can find a greater value that lies earlier in the array by wrapping around.

Prerequisites

Before you start

· Concepts used directly in the solution.

Monotonic stack. A stack of indices kept decreasing by value; pop when a greater value arrives.

Circular indexing. Using i % n to wrap the scan past the end of the array.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Circular rules

“How far can I wrap?”

At most once around — every other element is reachable within n - 1 steps.

“Strict greater?”

Yes — an equal value doesn't count.

The ideal opening — say it like this

This is next-greater-element, but the array wraps, so an element can be answered by something earlier in the array.

I run the monotonic stack over 2n indices using i mod n, pushing real indices only in the first pass.

When a larger value arrives, it resolves every smaller index still on the stack.

Understand the problem

Worked example — nums = [1, 2, 1]

i=0 (1): push 0                    stack [0]
i=1 (2): 2 > nums[0]=1 -> res[0]=2, pop; push 1   stack [1]
i=2 (1): push 2                    stack [1,2]
i=3 (1%3=0 -> nums=1): no pop
i=4 (1): no pop
i=5 (2): 2 > nums[2]=1 -> res[2]=2, pop           stack [1]
answer: [2, -1, 2]

Key observations

1Aha

Two passes handle the wrap

Scanning 2n indices with i % n lets an element be resolved by a greater value that appears earlier in the array, exactly what circularity allows.

2Aha

Push only in the first pass

Adding indices again in the second pass would double-count; the second pass only resolves pending indices.

3Aha

Still O(n)

Each index is pushed once and popped at most once across the doubled loop, so it's linear.

Brute force vs optimal

	Wrap-and-scan	Monotonic stack (2n)
Idea	For each i, scan up to n-1 steps with modulo	Decreasing-value index stack over 2n indices
Time	O(n^2)	O(n)
Space	O(1)	O(n)

Full code is in the Approaches selector below.

Summary

Key takeaway

Circular next-greater-element = the monotonic index stack run over 2n positions with i % n. Push indices only in the first pass; a larger incoming value resolves all smaller indices on the stack. O(n).

res = [-1]*n; stack = []
for i in 0 .. 2n-1:
    while stack and nums[stack.top] < nums[i % n]:
        res[stack.pop()] = nums[i % n]
    if i < n: stack.push(i)
return res