# Longest Consecutive Sequence

ArrayHash TableUnion Find

## # Solution

Let $n$ be the length of the array nums.

The brute force $O(n^3)$ solution is omitted.

### # Sort

Complexity

time: $O(n \log n)$
space: $O(1)$ (sort is in place)

def longestConsecutive(self, nums: List[int]) -> int:
if not nums: return 0
n = len(nums)
curr_seq = 1
res = 1
# sort the sequence in place
nums.sort()

for i in range(1, n):
# eliminate duplicates
if nums[i] != nums[i-1]:
# sequence is continued
if nums[i] == nums[i-1]+1:
curr_seq += 1
# start a new sequence
else:
res = max(res, curr_seq)
curr_seq = 1

return max(res, curr_seq)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Could you implement the $O(n)$ solution?

### # HashSet

Complexity

time: $O(n)$
space: $O(n)$

def longestConsecutive(self, nums: List[int]) -> int:
res = 0
hashset = set(nums)

for num in nums:
# find the start of sequence
if num - 1 not in hashset:
curr_num = num
curr_seq = 1
# sequence can be continued
while curr_num + 1 in hashset:
curr_num += 1
curr_seq += 1
# update longest consecutive sequence seen so far
res = max(res, curr_seq)

return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

## # Union Find (REDO)

Complexity

time: $O(n)$
space: $O(n)$

See more in Interview Algorithms and this LeetCode post (opens new window).

class Node:
def __init__(self, val):
self.val = val
self.parent = self
self.size = 1

class UnionFind:
def find(self, node):
if node.parent != node:
node.parent = self.find(node.parent)
return node.parent

def union(self, node1, node2):
parent_1 = self.find(node1)
parent_2 = self.find(node2)
if parent_1 != parent_2:
parent_2.parent = parent_1
parent_1.size += parent_2.size
return parent_1.size

class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
uf = UnionFind()
nodes = {}
max_size = 0
for num in nums:
if num not in nodes:
node = Node(num)
nodes[num] = node
size = 1
if num + 1 in nodes:
size = uf.union(node, nodes[num+1])
if num - 1 in nodes:
size = uf.union(node, nodes[num-1])
max_size = max(max_size, size)

return max_size

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37