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.
public int longestConsecutive(int[] nums) {
Set<Integer> numSet = new HashSet<>();
for (int num : nums) numSet.add(num);
int longestStreak = 0;
for (int num : numSet) {
if (!numSet.contains(num - 1)) {
int currentNum = num;
int currentStreak = 1;
while (numSet.contains(currentNum + 1)) {
currentNum += 1;
currentStreak += 1;
}
longestStreak = Math.max(longestStreak, currentStreak);
}
}
return longestStreak;
}Follow-up:
What if the input array is very large and we want to find the longest consecutive sequence in a streaming fashion?
