Longest Consecutive Sequence (LeetCode #128)

Challenge Statement

• 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.
• This challenge corresponds to LeetCode #128.

Constraints

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

Example 1:

Input: nums = [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

Input: nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
Output: 9

Solution

Below is my solution and some test cases. This solution has a linear time complexity O(n) and a linear space complexity O(n), where n is the length of the input list.