75. Longest Consecutive Sequence

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Input: An integer array nums (may be unsorted, may contain duplicates).

Output: Integer — length of longest consecutive sequence.

Examples

Example 1

Input: [100,4,200,1,3,2]
Output: 4
Explanation: Consecutive sequence: [1,2,3,4]. Length = 4.

Example 2

Input: [0,3,7,2,5,8,4,6,0,1]
Output: 9
Explanation: Sequence: [0,1,2,3,4,5,6,7,8]. Length = 9.

Example 3

Input: [1,2,3,4,5]
Output: 5
Explanation: All consecutive. Length = 5.