In this guide, you will get 503. Next Greater Element II LeetCode Solution with the best time and space complexity. The solution to Next Greater Element II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Given a circular integer array nums (i.e., the next element of nums[nums.length – 1] is nums[0]), return the next greater number for every element in nums.
The next greater number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn’t exist, return -1 for this number.
Example 1:
Input: nums = [1,2,1]
Output: [2,-1,2]
Explanation: The first 1’s next greater number is 2;
The number 2 can’t find next greater number.
The second 1’s next greater number needs to search circularly, which is also 2.
Example 2:
Input: nums = [1,2,3,4,3]
Output: [2,3,4,-1,4]
Constraints:
1 <= nums.length <= 104
-109 <= nums[i] <= 109
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
503. Next Greater Element II LeetCode Solution in C++
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
const int n = nums.size();
vector<int> ans(n, -1);
stack<int> stack; // a decreasing stack storing indices
for (int i = 0; i < n * 2; ++i) {
const int num = nums[i % n];
while (!stack.empty() && nums[stack.top()] < num)
ans[stack.top()] = num, stack.pop();
if (i < n)
stack.push(i);
}
return ans;
}
}; /* code provided by PROGIEZ */
503. Next Greater Element II LeetCode Solution in Java
class Solution {
public int[] nextGreaterElements(int[] nums) {
final int n = nums.length;
int[] ans = new int[n];
Arrays.fill(ans, -1);
Deque<Integer> stack = new ArrayDeque<>(); // a decreasing stack storing indices
for (int i = 0; i < n * 2; ++i) {
final int num = nums[i % n];
while (!stack.isEmpty() && nums[stack.peek()] < num)
ans[stack.pop()] = num;
if (i < n)
stack.push(i);
}
return ans;
}
} // code provided by PROGIEZ
503. Next Greater Element II LeetCode Solution in Python
class Solution:
def nextGreaterElements(self, nums: list[int]) -> list[int]:
n = len(nums)
ans = [-1] * n
stack = [] # a decreasing stack storing indices
for i in range(n * 2):
num = nums[i % n]
while stack and nums[stack[-1]] < num:
ans[stack.pop()] = num
if i < n:
stack.append(i)
return ans # code by PROGIEZ
