Medium

Next Greater Element II

LAB

For each value in circular nums, return the next greater value to its right, or -1 if none exists.

EXAMPLES

Example 1

Input
{
  "nums": [
    1,
    2,
    1
  ]
}

Output
[
  2,
  -1,
  2
]

FUNCTION SHAPE

nums: intArray→intArray

SOLUTION NOTE

Common trick for circular arrays: double up the array.

Reveal reference solution +

pythonREFERENCE

def nextGreaterElements(self, A: List[int]) -> List[int]:
    def ng(A):
        n = len(A)
        stack = []
        res = [n] * n
        for i in range(n):
            while stack and A[stack[-1]] < A[i]:
                res[stack[-1]] = i
                stack.pop()
            stack.append(i)
        return res

    NG = ng(A + A)
    n = len(A)
    res = [-1] * n
    for i in range(n):
        if NG[i] != 2*n:
            res[i] = A[NG[i] % n]
    return res

TimeO(n)

SpaceO(n)

Open on LeetCode ↗