**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**

- Add nums to a set. Then walk nums and for element x, if x-1 is in the set, then ignore it. If x -1 is not in set, then this means that x is the start of a streak and we walk the entire streak and capture its length.
- This is pure genius idea and makes sure that we process each streak exactly once which means O(N).
- https://discuss.leetcode.com/topic/15383/simple-o-n-with-explanation-just-walk-each-streak

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