Java O(N) with HashSet, 4 pass


#1

Gist of solution: Add every element to a set (1 pass). Copy that set to an array/arrayList.

Iterate over the array list. For each value in arrayList (1 pass), if the set contains the value, iterate downwards until you find a value not in the set, i.e. start of streak (1 pass). Iterate back upwards, while increasing count and removing from set (1 pass).

This way, when an already seen value comes up in your ArrayList iteration, you can just skip over it.

public class Solution {
	public int longestConsecutive(final List<Integer> a) {
	    Set<Integer> seen = new HashSet<>();
    
    for (int i: a) {
        seen.add(i); 
    }
    
    // duplicate, otherwise will get concurrent modification exception when removing, or lead to errors. 
    ArrayList<Integer> values = new ArrayList<>(seen); 
    
    int maxCount = 0; 
    for (int i = 0; i < values.size(); i++) {
        
        int current = values.get(i);
        if (!seen.contains(current)) continue; 
        
        // go backwards
        while (seen.contains(current)) {
            current--;
        }
        
        // set to first element in streak
        current++; 
        int count = 1;
        
        // go forwards, count + remove
        while (seen.contains(current)) {
            seen.remove(current);
            maxCount = Math.max(maxCount, count);
            count++;
            current++; 
        }
    }
    
    return maxCount; 
}

}