# Solution For Next Greater Element Ii

The Next Greater Element II problem on LeetCode asks us to find the next greater element for each element in a given array, but with the constraint that the array is circular. This means that the next greater element for the last element in a circular array is the first element in the same array. Similarly, the next greater element for the previous element of the first element is the last element in the array.

To solve this problem, we can use a stack to keep track of elements. We traverse the array twice to make it circular (i.e., we concatenate the array with itself). In the first traversal, we push each element of the array onto the stack. For each element, we check if the current element is greater than the top element of the stack. If it is, then we pop the stack and mark the popped element’s next greater element as the current element. We do this until we find an element greater than the current element or the stack becomes empty. We continue this process until the end of the first traversal.

In the second traversal, we follow a similar process, but this time we mark the last element as the next greater element for any element still remaining in the stack. This is done to handle the circular nature of the array. We then return the next greater elements for each element in the original array.

Here is the implementation in Python:

```python class Solution: def nextGreaterElements(self, nums: List[int]) -> List[int]: n = len(nums) stack = [] result = [-1] * n for i in range(n * 2): while stack and nums[i % n] > nums[stack[-1]]: result[stack.pop()] = nums[i % n] stack.append(i % n) return result```

The time complexity of this solution is O(n) since we traverse the array twice and push/pop each element onto/from the stack at most once. The space complexity is also O(n) since we need to store all elements in the stack.

## Step by Step Implementation For Next Greater Element Ii

```class Solution {
public int[] nextGreaterElements(int[] nums) {
int[] res = new int[nums.length];
Stack stack = new Stack<>();
for (int i = 2 * nums.length - 1; i >= 0; --i) {
while (!stack.empty() && nums[stack.peek()] <= nums[i % nums.length]) {
stack.pop();
}
res[i % nums.length] = stack.empty() ? -1 : nums[stack.peek()];
stack.push(i % nums.length);
}
return res;
}
}```
```class Solution:
def nextGreaterElements(self, nums: List[int]) -> List[int]:
# create an empty stack
stack = []
# create a result list of the same size as nums
result = [-1] * len(nums)
# loop through nums twice
for i in range(len(nums) * 2):
# loop through nums from the end
while stack and nums[stack[-1]] < nums[i % len(nums)]:
# pop the top element from the stack
# and insert its next greater element in the result list
result[stack.pop()] = nums[i % len(nums)]
# push the current element onto the stack
stack.append(i % len(nums))
# return the result list
return result```
```var nextGreaterElements = function(nums) {

// create an empty stack
let stack = [];

// create a result array with the same length as the input array
let result = new Array(nums.length).fill(-1);

// loop through the input array twice
for (let i = 0; i < nums.length * 2; i++) {

// store the current number
let num = nums[i % nums.length];

// while the stack is not empty and the top element of the stack is less than the current number
while (stack.length > 0 && stack[stack.length - 1] < num) {

// pop the top element from the stack
let popped = stack.pop();

// store the current number as the next greater element for the popped element
result[popped] = num;
}

// push the current number onto the stack
stack.push(num);
}

// return the result array
return result;
};```
```vector nextGreaterElements(vector& nums) {
int n = nums.size();
vector res(n, -1);
stack st;

for (int i = 0; i < 2*n; i++) {
int num = nums[i % n];
while (!st.empty() && nums[st.top()] < num) {
res[st.top()] = num;
st.pop();
}
if (i < n) st.push(i);
}
return res;
}```
```public class Solution {
public int[] NextGreaterElements(int[] nums) {
//Create a stack to store the indices of the elements
Stack stack = new Stack();
//Create an array to store the next greater element for each index
int[] res = new int[nums.Length];

for(int i = 2 * nums.Length - 1; i >= 0; i--)
{
//While the stack is not empty and the top element of the stack is less than the current element, pop the element from the stack
while(stack.Count != 0 && nums[stack.Peek()] <= nums[i % nums.Length])
{
stack.Pop();
}
//If the stack is empty, store -1 in the result array for the current index. Otherwise, store the next greater element for the current index.
res[i % nums.Length] = (stack.Count == 0) ? -1 : nums[stack.Peek()];
//Push the current index onto the stack
stack.Push(i % nums.Length);
}
//Return the result array
return res;
}
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]