3 Solutions for longest consecutive sequence
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Your algorithm should run in O(n) complexity.
Naive Solution: Use set to check consecutive elements
We use a
set to check whether one element exists in array. Iterate all the elments and try to find the longest sub-array in loop.
But the overall time complexity is O(N^2), which will time limited.
An Optimization on previous solution: reduce duplicated checking
The duplicated checking happened at a long consecutive array, suppose we have
3, 4, 5, 6, 7.
First we checked with 3, and then checked at 4, and 5 …
This could be avoided if we test whether i-1 has been checked.
Use union-find to store relationships of elements
union-find is a elegant data structure to store and query consecutive relationships.
U will store the next larger elements of one element.
Iterate with all the elements, try to find the largest element from one starting point, and the distance of two elements will be the number of consecutive elements.