Longest Consecutive Sequence
Given an unsorted array of integers, find the length of the longest consecutive sequence.
Constraints:
- 1 <= nums.length <= 10^4
- 0 <= nums[i] <= 10^9
Examples:
Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive sequence is [1, 2, 3, 4].
Input: [0,3,7,2,5,8,4,6,0,1]
Output: 9
Explanation: The longest consecutive sequence is [0, 1, 2, 3, 4, 5, 6, 7, 8].
Solutions
Hash Set
We use a hash set to store the numbers in the array. Then we iterate over the set and for each number, we check if it is the start of a sequence (i.e., `num - 1` is not in the set). If it is, we then check for the presence of `num + 1`, `num + 2`, etc. in the set and keep track of the length of the current sequence. We update the longest streak if the current sequence is longer.
def longestConsecutive(nums):
num_set = set(nums); longest_streak = 0; for num in num_set:
if num - 1 not in num_set:
current_num = num; current_streak = 1; while current_num + 1 in num_set:
current_num += 1; current_streak += 1; longest_streak = max(longest_streak, current_streak); return longest_streakFollow-up:
What if the input array is very large and we want to find the longest consecutive sequence in a streaming fashion?
