Coder's Cat

## LeetCode: Longest Consecutive Sequence

2020-08-02

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 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.

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