Next Greater Element II Solution

Problem

Given a circular integer array, find the next greater element for each position. The next greater element is the first value to the right that is strictly larger — and because the array is circular, you can scan past the last element and wrap back to the front. If no larger element exists anywhere in the array, return -1 for that position.

Example:

Input: nums = [1, 2, 1]
Output: [2, -1, 2]
Explanation: the first 1 sees 2 immediately to its right; 2 finds nothing greater even after wrapping around; the last 1 wraps and finds 2 at index 1.

Counter-example: for [3, 3, 3], the output is [-1, -1, -1] — every element is equal, and strict greater-than is never satisfied anywhere in the circular scan.

Intuition

For a linear array this problem is straightforward — scan right and stop. The circular boundary means any element might need to look all the way around the back of the array before finding a larger value, which is hard to handle in a single left-to-right pass. The insight is to treat the array as if it were written out twice end-to-end: iterating over indices 0 to 2n−1 with modular indexing (i % n) simulates that wrap-around perfectly. A monotone decreasing stack of indices tracks which elements are still waiting for their next greater value; whenever a larger element arrives, those waiting elements get resolved immediately.

Approach 1 — Brute Force

For each element, scan forward up to n−1 steps using modular indexing, stopping at the first value that is strictly greater.

Steps:

Initialize result of size n with -1.
For each index i from 0 to n−1, scan steps from 1 to n−1.
Compute neighbor = nums[(i + steps) % n].
If neighbor > nums[i], record it in result[i] and break out of the inner loop.
Return result.

1def nextGreaterElements(nums: List[int]) -> List[int]:
2    n = len(nums)
3    result = [-1] * n
4    for i in range(n):
5        for steps in range(1, n):
6            neighbor = nums[(i + steps) % n]
7            if neighbor > nums[i]:
8                result[i] = neighbor
9                break
10    return result

Time: O(n²) — each of the n elements may scan up to n−1 positions in the worst case.
Space: O(1) — no extra data structures beyond the output array.

Approach 2 — Monotonic Stack with Double Pass

Iterate over indices 0 to 2n−1 with modular indexing, maintaining a monotone decreasing stack of indices. When an incoming value is greater than the value at the stack's top, those waiting indices get their answer resolved.

Steps:

Initialize result of size n with -1 and an empty index stack.
For each i from 0 to 2n−1, compute actual = i % n.
While the stack is non-empty and nums[actual] > nums[stack.top()], pop the stack and set result[popped] = nums[actual].
Only push actual when i < n — this ensures each index enters as a candidate exactly once.
Return result.

1def nextGreaterElements(nums: List[int]) -> List[int]:
2    n = len(nums)
3    result = [-1] * n
4    stack = []  # indices whose next-greater is not yet found, in decreasing value order
5
6    for i in range(2 * n):
7        actual = i % n
8        while stack and nums[actual] > nums[stack[-1]]:
9            popped = stack.pop()
10            result[popped] = nums[actual]
11        if i < n:  # only enqueue each index once as a candidate
12            stack.append(actual)
13
14    return result

Time: O(n) — each index is pushed once and popped at most once across both simulated passes.
Space: O(n) — the stack holds at most n indices.

Complexity Summary

Approach	Time	Space	When to use
Brute Force	O(n²)	O(1)	Tiny arrays or when auxiliary memory is strictly forbidden
Monotonic Stack	O(n)	O(n)	Always preferred for any meaningful array size

Common Mistakes

Forgetting the circular wrap-around — iterating only 0 to n−1 and using nums[i+1] misses elements that need to look past the end; you must simulate two passes with modular indexing.
Pushing indices in the second pass — if you push to the stack for all 2n iterations instead of only when i < n, each index appears as a candidate twice and can get resolved with the wrong value.
Using nums[i] instead of nums[i % n] — once i >= n you read out of bounds; all array accesses must go through actual = i % n.
Building a monotone increasing stack — this resolves elements when a smaller value arrives (the pattern for "next smaller element"), not a larger one; the stack must stay decreasing so it pops when a greater value arrives.
Starting inner scan at steps = 0 — comparing an element to itself always satisfies >=, so every element would find itself as its own next greater and never return -1.

Next Greater Element II — Solution