3 Solutions for longest consecutive sequence
Challenge description
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Your algorithm should run in O(n) complexity.
Example:

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 subarray 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 i1 has been checked.

Use unionfind to store relationships of elements
unionfind
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.

Join my Email List for more insights, It's Free!😋