O(n) runtime & O(n) space solution with Hashmap and Deque


  • 0

    This solution ran 39 ms which is very solid, esp in python. It makes use of hashmaps and deque.

    As you walk through the list, you build a hashmap; the key of this hashmap is the number and the value is a "pointer" to a deque (this way many numbers can point to the same deque). You can check the consecutive property by whether or not there is the current num +/- 1 inside the hashmap that you're building. If the consecutive property doesn't hold, create a new deque. If the consecutive property holds true, there are two cases: Either there is only one adjacent consecutive number, or two adjacent consecutive numbers. In the first case, you simply merge the current num with the deque of the adjacent consecutive number. In the latter case, you have to merge the deques of both adjacent consecutive numbers into a single one.

    from collections import deque
    
    class Solution(object):
        def longestConsecutive(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            lookup = {}
            max_length = 0
            for num in nums:
                if num in lookup:
                    continue
                if num+1 in lookup and num-1 in lookup: # 2 adjacents
                    lookup[num-1].append(num)
                    lookup[num] = lookup[num-1] # merge num with lower adjacent
                    runner = num+1
                    while runner in lookup: # add higher adjacents to the lower deque
                        lookup[runner-1].append(runner)
                        lookup[runner] = lookup[runner-1]
                        runner += 1
                elif num+1 in lookup: # 1 adjacent
                    lookup[num+1].appendleft(num)
                    lookup[num] = lookup[num+1]
                elif num-1 in lookup: # 1 adjacent
                    lookup[num-1].append(num)
                    lookup[num] = lookup[num-1]
                else: # 0 adjacents
                    lookup[num] = deque([num])
                max_length = max(max_length, len(lookup[num]))
            return max_length
    

Log in to reply
 

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