less than 1 minute read

You are given a list of integers nums. Return a new list of the same length where the value at index i is set to the next element greater than nums[i] to its right, circling back to the front of the list if necessary. If there’s no number that’s greater, then it should be set to -1.

Constraints

  • n ≤ 100,000 where n is the length of nums

https://binarysearch.com/problems/Circular-Greater-Element-to-the-Right

ExamplesPermalink

Example 1Permalink

Input

  • nums = [3, 4, 0, 2]

Output

  • answer = [4, -1, 2, 3]

SolutionPermalink

class Solution:
def solve(self, nums):
# use a monotonic stack to store decreasing nums
stack = []
res = [-1] * len(nums)
for idx, num in enumerate(nums * 2):
while stack and nums[stack[-1]] < num:
# pop until we can store this num
# for each popped, set result to this num
# as this is the first num > popped
res[stack.pop()] = num
if idx < len(nums):
stack.append(idx)
return res

Categories:

Updated:

Leave a comment