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;
    }
}