Problem statement

https://leetcode.com/problems/next-greater-element-ii/

Solution

Similar to problem 0496 Next Greater Element I. Let us again keep not-increasing stack. Let us use the trick with duplication of array. Create result = [-1]*n and then iterate through duplicated array. We only update elements in result if we found next greater element, if we did not find it, it will remain equal to zero.

Complexity

Time complexity is O(n), because we put and remove from stack not more than 1 time, space complexity is O(n) for duplication of nums.

Code

class Solution:
    def nextGreaterElements(self, nums):
        stack, n = [], len(nums)
        result = [-1]*n
        
        for i, num in enumerate(nums + nums[:-1]):
            while stack and stack[-1][1] < num:
                a, b = stack.pop()
                result[a%n] = num
            stack.append((i, num))
        
        return result