6. Longest Consecutive Sequence
Oct 20, 2020
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
class Solution {
public int longestConsecutive(int[] nums) {
HashSet<Integer> set = new HashSet<>();
for(int n : nums){
set.add(n);
}
int sol = 0;
for(int n : nums) {
if(!set.contains(n-1)){
int temp = n;
int count=0;
while(set.contains(temp)) {
temp++;
count++;
}
sol = Math.max(sol, count);
}
}
return sol;
}
}