6. Longest Consecutive Sequence

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;
 
 }
}