Longest Consecutive Sequence
franklinqin0 ArrayHash TableUnion Find
# Solution
Let be the length of the array nums
.
The brute force solution is omitted.
# Sort
Complexity
time:
space: (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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Follow up
Could you implement the solution?
# HashSet
Complexity
time:
space:
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Union Find (REDO)
Complexity
time:
space:
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
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