Python O(n) time with comments. 7 Lines!


  • 0
    R

    This is using the typical way to solve circular array problems; i.e., go through the array twice. In the case of Python it is a list and not an array. There may be some incorrect entries the first round through, but these get corrected on the second pass.

    Also, rather than create a copy of the list with the list repeated, an pointer (index) is used that gets modded (%) by the length to find the correct place in the original list.

    class Solution(object):
        def nextGreaterElements(self, nums):
            """
            :type nums: List[int]
            :rtype: List[int]
            """
            # Create a stack and a list to hold the result
            stack = []; res = list(nums)
            
            # Go thourh the list twice, starting from the right
            for i in xrange(2*len(nums)-1, -1, -1):
                # If there is not a solution at the end of the stack; pop
                while stack and stack[-1] <= nums[i%len(nums)]: stack.pop()
                # If the stack was empty put -1
                if len(stack) == 0: res[i%len(nums)] = -1
                # If there was a soluton at the end of the stack use that
                else: res[i%len(nums)] = stack[-1]
                # append the current value to the stack
                stack.append(nums[i%len(nums)])
            return res
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.