Next Greater Element II

Problem

Given a CIRCULAR integer array, return the next-greater element for each index. If none exists, output -1 at that index.

Constraints

• 1 ≤ n ≤ 10⁴

Approach — Monotonic Stack

This is a Monotonic Stack problem. The idea: scan once and keep a stack whose order stays meaningful, popping elements as soon as a later value resolves them. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time, O(n) space.

Solution code

Python

class Solution:
    def nextGreaterElements(self, nums):
        n = len(nums)
        res = [-1] * n
        st = []
        for i in range(2 * n):
            while st and nums[st[-1]] < nums[i % n]:
                res[st.pop()] = nums[i % n]
            if i < n:
                st.append(i)
        return res

Java

import java.util.*;

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] out = new int[n];
        Arrays.fill(out, -1);
        Deque<Integer> stk = new ArrayDeque<>();

        for (int i = 0; i < 2 * n; i++) {
            int v = nums[i % n];
            while (!stk.isEmpty() && nums[stk.peek()] < v) {
                out[stk.pop()] = v;
            }
            if (i < n) stk.push(i);
        }
        return out;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.