Python O(m+n)

  • 0
    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
            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.