Data Structures & Algorithms · Stacks and Queues

Next Greater Element II: The Monotonic Stack Goes Circular

Q: How do you handle the circular array without copying it?

Iterate 2n virtual indices and map each one to a real position with idx = i % n. Indices n through 2n - 1 revisit positions 0 through n - 1, giving every element a view past the end of the array and back around to the start — exactly what circular traversal means. The array is never duplicated; the modulo simulates the doubled layout for free.

Q: Why does the loop run backwards from 2n − 1 instead of forwards?

Scanning right to left keeps a clean invariant: when the loop reaches index idx, the stack contains precisely the surviving candidates circularly to its right, because the second copy was processed first and primed the stack. A forward-scanning variant also works — push indices, resolve them when a larger value arrives — but the reverse version writes each answer directly and mirrors the non-circular algorithm most engineers learn first.

Q: Why does the solution pop when the stack top is equal, not just smaller?

Because the problem asks for the first strictly greater element. A value equal to the current one can never be its answer — and since the current element is just as tall and closer to future queries, the equal value can never be anyone else's answer either. Popping on <= keeps the stack strictly decreasing; using < breaks duplicate-heavy inputs, returning [3, 3, 3] for [3, 3, 3] instead of the correct [-1, -1, -1].

Q: What are the time and space complexity of Next Greater Element II?

O(n) time and O(n) space. The loop performs 2n iterations, and each element is pushed at most twice and popped at most twice, bounding total stack operations by 4n regardless of input shape. Space is the candidate stack plus the output array. The brute-force alternative — walking the circle from every index — is O(n²), which hurts at the problem's limit of 10⁴ elements.

Q: Does the stack store values or indices here?

Values. This formulation only needs to read the next greater value off the stack top, and the i < n guard already controls which positions receive answers — indices would add nothing. Store indices instead when the answer depends on position, as in Daily Temperatures, where you need the distance to the warmer day.

The circular monotonic stack solution to Next Greater Element II, explained: reverse-scan a doubled array, JavaScript code, walkthrough, and complexity.

July 12, 20268 min readBy Bhavesh Singh

monotonic stackcircular arraystackscircular monotonic stackleetcode medium

This article has an interactive companion

Don't just read it — step through it interactively, one state change at a time.

Open the Next Greater Element II visualizer

Next Greater Element II (LeetCode 503) takes the classic monotonic stack problem and bends the array into a circle. Now the last element can wrap around and find its answer at index 0 — and the clean "scan once, stack the candidates" recipe seems to break. How does a single pass see elements that come before the current one?

The fix is one of the most reusable tricks in array problems: simulate the circle by scanning twice, without ever copying the array. Iterate 2n virtual indices, map each back with i % n, and the wrap-around falls out of the arithmetic. Combine that with the monotonic stack from the non-circular version and every position resolves in O(n) — and if you can explain why the second pass is enough, you've genuinely understood monotonic stacks.

The problem

Given a circular integer array nums, return an array where answer[i] is the first element strictly greater than nums[i] when traversing forward, wrapping past the end back to the start. If no such element exists anywhere in the circle, answer[i] = -1.

text

Input:  nums = [1, 2, 1]
Output: [2, -1, 2]
// index 0: the 2 right next to it
// index 1: 2 is the maximum — nothing in the circle is greater → -1
// index 2: wraps around past index 0 and finds the 2 at index 1

Two words carry all the difficulty:

Circular — index n - 1's search continues at index 0. A plain left-to-right scan never sees those candidates.
Greater — strictly. In [3, 3, 3], nothing has a next greater; the answer is [-1, -1, -1], not [3, 3, 3].

The brute force baseline

For each index, walk forward around the circle until you hit something bigger or come all the way back.

javascript

function nextGreaterElements(nums) {
  const n = nums.length;
  const answer = new Array(n).fill(-1);

  for (let i = 0; i < n; i++) {
    for (let step = 1; step < n; step++) {
      const candidate = nums[(i + step) % n];
      if (candidate > nums[i]) {
        answer[i] = candidate;
        break;
      }
    }
  }

  return answer;
}

Correct, and the % n inside already hints at the real solution. But each element may scan the other n - 1 positions: O(n²) total. With n up to 10⁴, a descending array like [10000, 9999, ..., 1] forces nearly 10⁸ comparisons — every element walks almost the full circle before finding the maximum.

The key insight: double the scan, not the array

Strip away the circularity for a second. The non-circular version has a textbook answer: scan right to left while a stack keeps candidate values in strictly decreasing order. At each element, pop everything less than or equal to it — those values are smaller and farther away, so they can never be anyone's answer again. The survivor on top is the current element's next greater; then push the current element as a candidate for whoever comes next. Each value is pushed once, popped at most once: O(n).

Now the circular twist. Element i's search window is i+1 ... n-1 followed by 0 ... i-1 — conceptually, the array laid out twice in a row. You could literally build nums.concat(nums), but there's no need. Iterate virtual indices 2n - 1 down to 0 and read nums[i % n] — the modulo simulates the doubled array for free.

Scanning backwards, the two halves play different roles:

Ghost pass (i from 2n - 1 down to n): writes no answers. Its only job is to prime the stack, so wrap-around candidates already exist when the real indices arrive.
Real pass (i from n - 1 down to 0): the stack now holds exactly the elements circularly to the right of idx. Pop the non-greater values, peek the survivor, write the answer.

That's the circular monotonic stack: the linear invariant, a doubled iteration space, and a guard so only real indices get answers.

The optimal solution

This is the exact algorithm the interactive visualizer steps through:

javascript

function nextGreaterElements(nums) {
    const n = nums.length;
    const answer = new Array(n).fill(-1);
    const stack = [];

    for (let i = 2 * n - 1; i >= 0; i--) {
        const idx = i % n;
        while (stack.length > 0 && stack[stack.length - 1] <= nums[idx]) {
            stack.pop();
        }
        if (i < n && stack.length > 0) {
            answer[idx] = stack[stack.length - 1];
        }
        stack.push(nums[idx]);
    }

    return answer;
}

Three details are load-bearing:

<= in the pop condition. Equal values are popped too, because "next greater" is strict. Keep < and equal neighbors masquerade as answers.
The i < n guard. Answers are written only during the real pass, when the stack represents the full circular window.
Push on every iteration. Each element enters the stack twice — once per pass — which is what lets the real pass see wrapped candidates. And because answer starts at -1, maximum elements need no special handling: their slot is never overwritten.

Walkthrough: nums = [1, 2, 1]

Here n = 3, so i runs from 5 down to 0. Stack is written bottom → top.

i	idx	nums[idx]	Pops (top ≤ current)	Write answer?	Stack after push	answer
5	2	1	—	ghost pass — skip	[1]	[-1, -1, -1]
4	1	2	pop 1	ghost pass — skip	[2]	[-1, -1, -1]
3	0	1	—	ghost pass — skip	[2, 1]	[-1, -1, -1]
2	2	1	pop 1	answer[2] = 2	[2, 1]	[-1, -1, 2]
1	1	2	pop 1, pop 2	stack empty → stays -1	[2]	[-1, -1, 2]
0	0	1	—	answer[0] = 2	[2, 1]	[2, -1, 2]

Two decisive moments. At i = 2, index 2 pops the equal 1 (its own ghost copy) and finds 2 beneath it — a value that entered during the ghost pass. That is the wrap-around. At i = 1, the value 2 empties the whole stack: nothing in the circle is greater, so its initialized -1 stands. Final answer: [2, -1, 2].

Complexity

Approach	Time	Space	Why
Brute force circular scan	O(n²)	O(1)	each element may walk the other n − 1 positions
Concatenate `nums + nums`, linear NGE	O(n)	O(n) array copy + stack	correct, but physically doubles the input
Doubled reverse scan + monotonic stack	O(n)	O(n)	2n visits; each value pushed and popped at most twice

The while loop looks nested but isn't quadratic: the run makes exactly 2n pushes, so there can be at most 2n pops, however they cluster. That amortized argument — total pops bounded by total pushes — is the standard proof for every monotonic stack problem, and worth stating explicitly in an interview.

Common mistakes

Popping with < instead of <=. Equal values must be discarded — they aren't "greater". With <, the input [3, 3, 3] returns [3, 3, 3] instead of [-1, -1, -1].
Forgetting % n on the read. In JavaScript, nums[i] for i >= n is undefined, and stack[top] <= undefined is silently false — no error, no pops, just quietly wrong answers.
Looping only n times. Without the second pass, the tail never sees the head: [4, 3, 2, 1] comes back all -1 instead of [-1, 4, 4, 4].
Skipping the -1 initialization. The algorithm never writes to positions with no greater element (the array's maximums). If answer starts empty or zeroed, those slots hold garbage.
Actually concatenating the array. nums.concat(nums) works but allocates a second copy — and you still need % n when writing answers. The virtual-index loop gives you the doubled view for free.

Where this pattern shows up next

This problem sits at the top of a natural stack progression:

Remove Outermost Parentheses — the gentlest entry point: depth tracking is a stack reduced to a counter.
Evaluate Reverse Polish Notation — the stack as an evaluation machine, popping operands instead of candidates.
Next Greater Element I — the non-circular original, where the same decreasing stack feeds a hash map of answers.
Daily Temperatures — the same question asked about distance instead of value, which flips the stack to storing indices.

The circular trick itself — 2n iterations with i % n — transfers to any wrap-around array problem, from circular subarray sums to rotated-array searches. To watch the ghost pass prime the stack and the real pass drain it, step through it interactively.

FAQ

How do you handle the circular array without copying it?

Iterate 2n virtual indices and map each one to a real position with idx = i % n. Indices n through 2n - 1 revisit positions 0 through n - 1, giving every element a view past the end of the array and back around to the start — exactly what circular traversal means. The array is never duplicated; the modulo simulates the doubled layout for free.

Why does the loop run backwards from 2n − 1 instead of forwards?

Scanning right to left keeps a clean invariant: when the loop reaches index idx, the stack contains precisely the surviving candidates circularly to its right, because the second copy was processed first and primed the stack. A forward-scanning variant also works — push indices, resolve them when a larger value arrives — but the reverse version writes each answer directly and mirrors the non-circular algorithm most engineers learn first.

Why does the solution pop when the stack top is equal, not just smaller?

Because the problem asks for the first strictly greater element. A value equal to the current one can never be its answer — and since the current element is just as tall and closer to future queries, the equal value can never be anyone else's answer either. Popping on <= keeps the stack strictly decreasing; using < breaks duplicate-heavy inputs, returning [3, 3, 3] for [3, 3, 3] instead of the correct [-1, -1, -1].

What are the time and space complexity of Next Greater Element II?

O(n) time and O(n) space. The loop performs 2n iterations, and each element is pushed at most twice and popped at most twice, bounding total stack operations by 4n regardless of input shape. Space is the candidate stack plus the output array. The brute-force alternative — walking the circle from every index — is O(n²), which hurts at the problem's limit of 10⁴ elements.

Does the stack store values or indices here?

Values. This formulation only needs to read the next greater value off the stack top, and the i < n guard already controls which positions receive answers — indices would add nothing. Store indices instead when the answer depends on position, as in Daily Temperatures, where you need the distance to the warmer day.

Make it stick: run this one yourself

Don't just read it — step through it interactively, one state change at a time.

Open the Next Greater Element II visualizer

The problem#

The brute force baseline#

The key insight: double the scan, not the array#

The optimal solution#

Walkthrough: nums = [1, 2, 1]#

Complexity#

Common mistakes#

Where this pattern shows up next#

FAQ#

How do you handle the circular array without copying it?#

Why does the loop run backwards from 2n − 1 instead of forwards?#

Why does the solution pop when the stack top is equal, not just smaller?#

What are the time and space complexity of Next Greater Element II?#

Does the stack store values or indices here?#

Related articles