Longest Consecutive Sequence | Leetcode

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

---

Solution: Put all the numbers into a hashset. Then for each number, go in increasing order and in decreasing order to find all adjacent numbers. Keep track of the maximum adjacent length found so far. Remove each number as you encounter it as you will never need it again.

public class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) return 0;

        Set<Integer> set = new HashSet<>();
        for (int i: nums) set.add(i);
        
        int longest = 1;
        
        do {
            // A not-so-elegant way to extract a random element from the set.
            int n = set.iterator().next();
            set.remove(n);

            int length = 1;
            
            for (int i = n + 1; set.contains(i); i++) {
                length++;
                set.remove(i);
            }

            for (int i = n - 1; set.contains(i); i--) {
                length++;
                set.remove(i);
            }
            
            if (length > longest) longest = length;
        } while (!set.isEmpty());
        
        return longest;
    }
}