128. Longest Consecutive Sequence
Tags: ‘Array’, ‘Union Find’
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Your algorithm should run in O(n) complexity.
Example:
Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
Solution
Dynamically build string using HashSet
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num: nums) {
set.add(num);
}
int result = 0;
for (int num: nums) {
if (!set.contains(num-1)) { // make sure it's start
int curr = num;
int currStreak = 1;
while (set.contains(curr + 1)) {
curr += 1;
currStreak += 1;
}
result = Math.max(result, currStreak);
}
}
return result;
}