Approach: Monotonic stack over 2n

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

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

Full Solution — all languages

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

import java.util.*;
class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        Arrays.fill(res, -1);
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = 0; i < 2 * n; i++) {
            int cur = nums[i % n];
            while (!st.isEmpty() && nums[st.peek()] < cur) res[st.pop()] = cur;
            if (i < n) st.push(i);
        }
        return res;
    }
}

#include <bits/stdc++.h> using namespace std;
class Solution {
    public: vector<int> nextGreaterElements(vector<int>& nums) {
        int n = (int)nums.size();
        vector<int> res(n, -1);
        vector<int> st;
        for (int i = 0; i < 2 * n; i++) {
            int cur = nums[i % n];
            while (!st.empty() && nums[st.back()] < cur) {
                res[st.back()] = cur;
                st.pop_back();
            }
            if (i < n) st.push_back(i);
        }
        return res;
    }
};

/**
 * @param {number[]} nums
 * @return {number[]}
 */ var nextGreaterElements = function(nums) {
    const n = nums.length;
    const res = new Array(n).fill(-1);
    const st = [];
    for (let i = 0; i < 2 * n; i++) {
        const cur = nums[i % n];
        while (st.length && nums[st[st.length - 1]] < cur) res[st.pop()] = cur;
        if (i < n) st.push(i);
    }
    return res;
};

Next Greater Element II

Example 1

Example 2

Constraints