Longest Consecutive Sequence
Statement
Given an unsorted integers array numbers, find the length of the longest consecutive sequence of integers. Two integers x and y are consecutive if the difference between them is equal to 1.
Constraints
- 0 ≤
numbers.length()≤ 10³ - -10⁶ ≤
numbers[i]≤ 10⁶
Solution
"""
production algorithm
"""
class Solution:
def longest_consecutive_sequence(self, numbers):
"""
time complexity O(n)
space complexity O(n)
"""
unionfind = UnionFind(numbers)
for number in numbers:
if number + 1 in unionfind.parent:
unionfind.union(number, number + 1)
return unionfind.max_size
class UnionFind:
def __init__(self, numbers):
self.parent = {number: number for number in numbers}
self.size = {number: 1 for number in numbers}
self.max_size = 1
def find(self, x):
"""
time complexity O(⍺(n))
space complexity O(n)
"""
if not self.parent[x] == x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
"""
time complexity O(⍺(n))
space complexity O(n)
"""
rootx = self.find(x)
rooty = self.find(y)
if not rootx == rooty:
if self.size[rootx] < self.size[rooty]:
rooty, rootx = rootx, rooty
self.parent[rooty] = rootx
self.size[rootx] += self.size[rooty]
self.max_size = max(self.max_size, self.size[rootx])"""
unit tests
"""
from unittest import TestCase
from algorithms.union_find.longest_consecutive_sequence.solution import Solution
class SolutionTestCase(TestCase):
def test_zero_consecutive_integers(self):
# Given
numbers = [-44, -31, -12, 7, 18, -40, 25, -16, 33,
10, -27, 36, -3, 14, -20, 42, -8, 20, -37, 28]
solution = Solution()
# When
actual = solution.longest_consecutive_sequence(numbers)
# Then
expected = 1
self.assertEqual(actual, expected)
def test_some_consecutive_integers(self):
# Given
numbers = [-44, -42, -12, -41, 18, -40, 25, -43, -
10, 10, 11, 9, 12, 14, -20, 42, -8, -9, -7, 28]
solution = Solution()
# When
actual = solution.longest_consecutive_sequence(numbers)
# Then
expected = 5
self.assertEqual(actual, expected)
def test_all_consecutive_integers(self):
# Given
numbers = [-10, -9, -8, -7, -6, -5, -4, -
3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
solution = Solution()
# When
actual = solution.longest_consecutive_sequence(numbers)
# Then
expected = 20
self.assertEqual(actual, expected)Strategy
Union Find.
Explanation
The algorithm uses a UnionFind data structure. Since the integer array has arbitrary and possibly nonconsecutive integers, dictionaries are used to represent the disjoint sets, rather than lists. Another field max_size is also maintained by the UnionFind, to hold the maximum size of any disjoint set.
The algorithm iterates each integer. If a consecutive integer of the current integer of iteration exists in the UnionFind, then a union of the two integers occurs in the UnionFind. The max_size of any disjoint set is updated during a union of disjoint sets.
After iteration of the integer completes, max_size is the length of the longest consecutive sequence of integers.
Time Complexity
The algorithm iterates all integers. At most, for each integer a UnionFind operation occurs. The time complexity of UnionFind operations is amortized O(⍺(n)), where ⍺(n) is the inverse Ackerman function. Therefore, the time complexity of the algorithm is O(n × ⍺(n)), or simply O(n), where n is the number of integers.
Space Complexity
The UnionFind uses auxiliary space for each integer. Therefore, the auxiliary space of the algorithm is O(n).
