128. Longest Consecutive Sequence

Leetcode 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.

/** Given an unsorted array of integers,
 * find the length of the longest consecutive elements sequence.
 *
 * https://leetcode.com/problems/longest-consecutive-sequence/description/
 */
public class Q128LongestConsecutiveSequence {
    public int longestConsecutive(int[] nums) {
        HashMap<Integer, Integer> dict = new HashMap<>();
        HashMap<Integer, Integer> count = new HashMap<>();
        for (int num : nums) {
            dict.put(num, num);
            count.put(num, 1);
        }

        for (int num : nums) {
            if (dict.containsKey(num + 1))
                union(num,num + 1, dict, count);
            if (dict.containsKey(num - 1))
                union(num, num - 1, dict, count);
        }

        int max = 0;

        for (int num : nums) {
            max = Math.max(count.get(num), max);
        }
        return max;


    }

    private void union(int i, int j, HashMap<Integer, Integer> dict, HashMap<Integer, Integer> count) {
        int rooti = root(i, dict);
        int rootj = root(j, dict);
        if (rooti != rootj) {
            if (count.get(rooti) < count.get(rootj)) {
                dict.replace(rooti, rootj);
                count.replace(rootj, count.get(rooti) + count.get(rootj));
            } else {
                dict.replace(rootj, rooti);
                count.replace(rooti, count.get(rooti) + count.get(rootj));
            }

        }
    }

    private int root(int i, HashMap<Integer, Integer> dict) {
        while (i != dict.get(i)) {
            if (dict.containsKey(dict.get(i)))
                dict.replace(i, dict.get(dict.get(i)));
            i = dict.get(i);
        }
        return i;
    }
}