Next Greater Element II — Solution in Python, Java & C++
Next Greater Element II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Next Greater Element II is a medium coding problem on arrays, stack and monotonic stack.
- Difficulty: Medium
- Topics: Arrays, Stack, Monotonic Stack
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a circular integer array nums, return the next greater number for every element. Searching wraps around the array; if no greater number exists, output -1 for that element.
Example 1
Input: nums = [1,2,1]
Output: [2,-1,2]
Explanation: The last 1 wraps around to find 2.
Example 2
Input: nums = [1,2,3,4,3]
Output: [2,3,4,-1,4]
Constraints
1 <= nums.length <= 30-100 <= nums[i] <= 100
Hints for Next Greater Element II
Hint 1
Iterate the array twice (indices modulo n) to simulate the wrap-around.
Hint 2
Only push indices during the first pass; the second pass just resolves.
How to solve Next Greater Element II
This is the standard monotonic-stack scan with one twist: the search wraps. Rather than physically concatenating the array to itself, walk 2n steps and index with i % n. The second lap gives every element left unresolved its chance to see the elements that come before it in the original order.
Approach
- Fill the answer array with
-1, the value for elements that never find anything greater. - Keep a stack of indices whose next greater element is still unknown.
- Loop
ifrom0to2n - 1and takex = nums[i % n]. - While the stack is non-empty and the value at the top index is less than
x, pop and set that index's answer tox. - Push
ionly whilei < n. The second lap resolves; it never adds new work.
Why it works
Two laps suffice because the next greater element is at most n - 1 steps away — beyond that you are back where you started. Restricting pushes to the first lap keeps exactly one stack entry per index, so no index is answered twice and the second lap only drains what the first left behind. Whatever survives both laps is a maximum of the array and correctly keeps -1.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Pushing during the second lap is the classic bug: indices get duplicated and can be overwritten with a later, non-nearest value.
- Store indices, not values — you need the position to write the answer, and duplicate values are allowed here.
- Use
nums[i % n]for the value but the rawi < ntest for pushing; mixing the two up breaks the wrap.
Reference solution
Python
from typing import List
def nextGreaterElements(nums: List[int]) -> List[int]:
n = len(nums)
out = [-1] * n
st = []
for i in range(2 * n):
x = nums[i % n]
while st and nums[st[-1]] < x:
out[st.pop()] = x
if i < n:
st.append(i)
return outJava
public static int[] nextGreaterElements(int[] nums) {
int n = nums.length;
int[] out = new int[n];
Arrays.fill(out, -1);
Deque<Integer> st = new ArrayDeque<>();
for (int i = 0; i < 2 * n; i++) {
int x = nums[i % n];
while (!st.isEmpty() && nums[st.peek()] < x) out[st.pop()] = x;
if (i < n) st.push(i);
}
return out;
}C++
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
vector<int> out(n, -1);
vector<int> st;
for (int i = 0; i < 2 * n; i++) {
int x = nums[i % n];
while (!st.empty() && nums[st.back()] < x) {
out[st.back()] = x;
st.pop_back();
}
if (i < n) st.push_back(i);
}
return out;
}JavaScript
var nextGreaterElements = function(nums) {
const n = nums.length;
const out = new Array(n).fill(-1);
const st = [];
for (let i = 0; i < 2 * n; i++) {
const x = nums[i % n];
while (st.length > 0 && nums[st[st.length - 1]] < x) out[st.pop()] = x;
if (i < n) st.push(i);
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Stack Data Structure