Python O(m+n)


  • 0
    A
    class Solution(object):
        def nextGreaterElement(self, findNums, nums):
            """
            :type findNums: List[int]
            :type nums: List[int]
            :rtype: List[int]
            """
            # Time: O(m+n)
            # Space: O(m+n). m for hash table, n for stack
            nge_map = {}
            stk = []  # stack
            for y in nums:  # O(2n), push and pop for each y
                while stk and stk[-1] < y:
                    nge_map[stk.pop()] = y
                stk.append(y)
            return [nge_map.get(x, -1) for x in findNums]  # O(m)
    

Log in to reply
 

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