Longest Consecutive Sequence
Given an array of integers nums, return the length of the longest consecutive sequence of elements that can be formed.
A consecutive sequence is a sequence of elements where each element is exactly 1 greater than the previous element. The elements do not have to be consecutive in the original array.
You must write an algorithm that runs in O(n) time.
Example 1:
Input: nums = [2,20,4,10,3,4,5]
Output: 4
Explanation: The longest consecutive sequence is [2,3,4,5].
Example 2:
Input: nums = [0,3,2,5,4,6,1,1]
Output: 7
Recommended time and space complexity
You should aim for a solution with O(n) time complexity and O(n) space complexity, where n is the size of the input array.
Hint 1
Sorting the array would give you an O(n log n) solution. How can you achieve O(n)?
Hint 2
Use a hash set for instant number lookup. For each number, check if a number one greater exists.
Hint 3
Optimize the search by starting only from numbers that can be the beginning of a sequence (i.e., when the number one less doesn't exist in the set).