keetcoder

# 503. Next Greater Element II

LeetCode Problem Link (opens new window)

Given a circular array (the next element of the last element is the first element of the array), output the next greater number for every element. The next greater number of a number x is the first greater number to its traversing-order-next in the array, which means you should search circularly to find its next greater number. If it doesn't exist, output -1 for this number.

Example 1:

  • Input: [1,2,1]
  • Output: [2,-1,2]
  • Explanation: The next greater number of the first 1 is 2; for number 2 no next greater number exists; the next greater number of the second 1 needs to be searched circularly, which is also 2.

Note:

  • 1 <= nums.length <= 10^4
  • -10^9 <= nums[i] <= 10^9

# Solution

Before solving this problem, it's recommended to solve 0739.Daily Temperatures (opens new window) and 0496.Next Greater Element I (opens new window).

This problem is very similar to 0739.Daily Temperatures (opens new window).

However, this problem involves a circular array.

About the explanation of monotonic stack, I have already covered it in detail in the solution for 0739.Daily Temperatures (opens new window).

Here, I will focus on how to handle circular arrays.

Some might think that directly concatenating two arrays and then using a monotonic stack to find the next greater number would solve the issue!

Indeed, it is possible!

You can concatenate the nums array with itself, use a monotonic stack to compute the next greater number for each element, and finally resize the result array to the original array's size.

Here is the code:

// Version 1
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        // Concatenate a new nums
        vector<int> nums1(nums.begin(), nums.end());
        nums.insert(nums.end(), nums1.begin(), nums1.end());
        // Initialize result with the new nums' size
        vector<int> result(nums.size(), -1);
        if (nums.size() == 0) return result;

        // Start monotonic stack
        stack<int> st;
        st.push(0);
        for (int i = 1; i < nums.size(); i++) { 
            if (nums[i] < nums[st.top()]) st.push(i); 
            else if (nums[i] == nums[st.top()]) st.push(i);
            else { 
                while (!st.empty() && nums[i] > nums[st.top()]) {
                    result[st.top()] = nums[i];
                    st.pop();
                }
                st.push(i);
            }
        }
        // Finally, resize result to the original array size
        result.resize(nums.size() / 2);
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

This approach is indeed straightforward, but there are a lot of unnecessary operations, such as modifying the nums array, and you need to resize the result array at the end.

Resizing is not time-consuming as it's an O(1) operation, but expanding the nums array equivalent to an O(n) operation.

Actually, you don't have to expand nums but simulate traversing two rounds of nums during the iteration.

Here is the code:

// Version 2
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> result(nums.size(), -1);
        if (nums.size() == 0) return result;
        stack<int> st;
        st.push(0);
        for (int i = 1; i < nums.size() * 2; i++) { 
            // Simulating traversing two rounds of nums, notice that all operations use i % nums.size()
            if (nums[i % nums.size()] < nums[st.top()]) st.push(i % nums.size());
            else if (nums[i % nums.size()] == nums[st.top()]) st.push(i % nums.size()); 
            else {
                while (!st.empty() && nums[i % nums.size()] > nums[st.top()]) {
                    result[st.top()] = nums[i % nums.size()];
                    st.pop();
                }
                st.push(i % nums.size());
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Version two not only simplifies the code but also avoids unnecessary operations compared to version one!

Finally, here’s a concise version of the monotonic stack, consolidating the three conditions:

// Version 2
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> result(nums.size(), -1);
        if (nums.size() == 0) return result;
        stack<int> st;
        for (int i = 0; i < nums.size() * 2; i++) {
            // Simulating traversing two rounds of nums, notice that all operations use i % nums.size()
            while (!st.empty() && nums[i % nums.size()] > nums[st.top()]) {
                result[st.top()] = nums[i % nums.size()];
                st.pop();
            }
            st.push(i % nums.size());
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# Other Language Versions

# Java:

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        // Edge case check
        if(nums == null || nums.length <= 1) {
            return new int[]{-1};
        }
        int size = nums.length;
        int[] result = new int[size]; // To store results
        Arrays.fill(result,-1); // Default initialize all to -1
        Stack<Integer> st= new Stack<>(); // Stack to store indices of nums
        for(int i = 0; i < 2*size; i++) {
            while(!st.empty() && nums[i % size] > nums[st.peek()]) {
                result[st.peek()] = nums[i % size]; // Update result
                st.pop(); // Pop top
            }
            st.push(i % size);
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# Python:

Version One:

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        dp = [-1] * len(nums)
        stack = []
        for i in range(len(nums)*2):
            while(len(stack) != 0 and nums[i%len(nums)] > nums[stack[-1]]):
                    dp[stack[-1]] = nums[i%len(nums)]
                    stack.pop()
            stack.append(i%len(nums))
        return dp
1
2
3
4
5
6
7
8
9
10

Version Two: Optimization for Version One

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        res = [-1] * len(nums)
        stack = []
        # First traversal of nums
        for i, num in enumerate(nums):   
            while stack and num > nums[stack[-1]]:
                res[stack[-1]] = num
                stack.pop()
            stack.append(i)
        # At this point, the stack still has remnants, with some numbers needing updates for "no next greater number"
        # Second traversal of nums
        for num in nums:
            # If the stack is empty, all numbers have a next greater element, so return the result   
            if not stack:   
                return res
            while stack and num > nums[stack[-1]]:
                res[stack[-1]] = num
                stack.pop()
            # Do not add numbers that already have a next greater element to the stack, this prevents redundant assignments; only attempt to find the next greater element for leftovers from the first traversal.
        # Finally, some larger numbers may not have a next greater element, return the result
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# Go:

// Version one
func nextGreaterElements(nums []int) []int {
    // Concatenate a new nums
    numsNew := make([]int, len(nums) * 2)
    copy(numsNew, nums)
    copy(numsNew[len(nums):], nums)
    // Initialize result with a new nums size
    result := make([]int, len(numsNew))
    for i := range result {
        result[i] = -1
    }
    
    // Start monotonic stack
    st := []int{0}
    for i := 1; i < len(numsNew); i++ {
        if numsNew[i] < numsNew[st[len(st)-1]] {
            st = append(st, i)
        } else if numsNew[i] == numsNew[st[len(st)-1]] {
            st = append(st, i)
        } else {
            for len(st) > 0 && numsNew[i] > numsNew[st[len(st)-1]] {
                result[st[len(st)-1]] = numsNew[i]
                st = st[:len(st)-1]
            }
            st = append(st, i)
        }
    }
    result = result[:len(result)/2]
    return result
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// Version two
func nextGreaterElements(nums []int) []int {
    length := len(nums)
    result := make([]int,length)
    for i:=0;i<len(result);i++{
        result[i] = -1
    }
    // Monotonically decreasing, store indices
    stack := make([]int, 0)
    for i:=0; i < length*2; i++{
        for len(stack) > 0 && nums[i%length] > nums[stack[len(stack)-1]]{
            index := stack[len(stack)-1]
            stack = stack[:len(stack)-1] // pop
            result[index] = nums[i%length]
        }
        stack = append(stack, i%length)
    }
    return result
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# JavaScript:

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var nextGreaterElements = function (nums) {
  const len = nums.length;
  let stack = [];
  let res = Array(len).fill(-1);
  for (let i = 0; i < len * 2; i++) {
    while (
      stack.length &&
      nums[i % len] > nums[stack[stack.length - 1]]
    ) {
      const index = stack.pop();
      res[index] = nums[i % len];
    }
    stack.push(i % len);
  }
  return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# TypeScript:

function nextGreaterElements(nums: number[]): number[] {
    const length: number = nums.length;
    const stack: number[] = [];
    stack.push(0);
    const resArr: number[] = new Array(length).fill(-1);
    for (let i = 1; i < length * 2; i++) {
        const index = i % length;
        let top = stack[stack.length - 1];
        while (stack.length > 0 && nums[top] < nums[index]) {
            resArr[top] = nums[index];
            stack.pop();
            top = stack[stack.length - 1];
        }
        if (i < length) {
            stack.push(i);
        }
    }
    return resArr;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# Rust:

impl Solution {
    pub fn next_greater_elements(nums: Vec<i32>) -> Vec<i32> {
        let mut ans = vec![-1; nums.len() * 2];
        let mut stack = vec![];
        let double = nums.repeat(2);
        for (idx, &i) in double.iter().enumerate() {
            while !stack.is_empty() && double[*stack.last().unwrap()] < i {
                let pos = stack.pop().unwrap();
                ans[pos] = i;
            }
            stack.push(idx);
        }
        ans.into_iter().take(nums.len()).collect()
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Version Two:

impl Solution {
    pub fn next_greater_elements(nums: Vec<i32>) -> Vec<i32> {
        let (mut stack, mut res) = (vec![], vec![-1; nums.len()]);

        for i in 0..nums.len() * 2 {
            while let Some(&top) = stack.last() {
                if nums[i % nums.len()] <= nums[top] {
                    break;
                }
                let saved_index = stack.pop().unwrap();
                res[saved_index] = nums[i % nums.len()];
            }
            stack.push(i % nums.len());
        }

        res
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Last updated:: 9/4/2025, 3:19:38 PM

← 4. Trapping Rain Water →

Copyright © 2025 keetcoder