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

• 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
``````

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