# Python solution with detailed explanation

• Solution

Longest Consecutive Sequence https://leetcode.com/problems/longest-consecutive-sequence/

Algorithm 1

• Add all the nums to a dictionary such that dictionary[num] = True.
• For every element k, move up as far as you can go and then move down as far as you can go down. Invalidate the elements as you do this up and down walk. This makes sure that a number is processed just once for its longest streak and gives us a O(N) solution.
``````class Solution(object):
def longestConsecutive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
table, max_run = {k:True for k in nums}, 0
for k in table:
if table[k]:
# Move up
mid = k
while k in table and table[k]:
table[k], k = False, k-1
upper_run = mid-k
# Move down
k = mid + 1
while k in table and table[k]:
table[k], k = False, k+1
lower_run = k-mid-1
max_run = max(max_run, upper_run + lower_run)
return max_run
``````

Algorithm 2

``````class Solution(object):
def longestConsecutive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
cache, max_run = set(nums), 0
for x in nums:
if x-1 not in cache:
y = x
while y in cache:
y += 1
max_run = max(max_run, y-x)
return max_run
``````

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