LeetCode - Algorithms - 128. Longest Consecutive Sequence

Hard problem. Exercise for union-find. Almost done by myself, with help of union-find by Robert Sedgewick and Kevin Wayne.

Problem

128. Longest Consecutive Sequence

Java

union–find

© 1.5 Case Study: Union-Find Copyright © 2000–2019 Robert Sedgewick and Kevin Wayne. All rights reserved.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
class Solution {
    public int longestConsecutive(int[] nums) {
        int[] arr = removeDuplicates(nums);
        int N = arr.length;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i=0; i<N; i++) {
            if (!map.containsKey(arr[i]-1)) map.put(arr[i]-1, i);
            if (!map.containsKey(arr[i]+1)) map.put(arr[i]+1, i);
        }
        int len = 0;
        UF uf = new UF(N);
        for(int i=0; i<N; i++) {
            if (map.containsKey(arr[i])) {
                uf.union(i, map.get(arr[i]));
            }
        }
        int[] parent = uf.parent();
        Map<Integer,Integer> tmpMap = new HashMap<Integer, Integer>();
        int k;
        for(int i=0; i<parent.length; i++) {
            k = parent[i];
            if (tmpMap.containsKey(parent[i]))
                tmpMap.put(k, tmpMap.get(k)+1);
            else
                tmpMap.put(k, 1);
        }
        for(Integer n : tmpMap.values()) {
            if (n>len)
                len = n;
        }

        return len;        
    }
    
    private int[] removeDuplicates(int[] input) {
        if (input == null || input.length <= 0) {
            return input;
        }
        Set<Integer> aSet = new HashSet<>(input.length);
        for (int i : input) {
            aSet.add(i);
        }
        int[] a = new int[aSet.size()];
        int i=0;
        for(Integer x : aSet)
            a[i++] = x;
        return a;
    }
}

/**
 * Weighted quick-union by rank with path compression by halving.
 * @author Robert Sedgewick
 * @author Kevin Wayne
 * Algorithms, 4th edition textbook code and libraries
 * https://github.com/kevin-wayne/algs4
 */
class UF {
    private int[] parent;
    private byte[] rank;
    private int count;

    public UF(int n) {
        if (n < 0) throw new IllegalArgumentException();
        count = n;
        parent = new int[n];
        rank = new byte[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    public int find(int p) {
        validate(p);
        while (p != parent[p]) {
            parent[p] = parent[parent[p]];
            p = parent[p];
        }
        return p;
    }

    public int count() {
        return count;
    }

    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ) return;

        if      (rank[rootP] < rank[rootQ]) parent[rootP] = rootQ;
        else if (rank[rootP] > rank[rootQ]) parent[rootQ] = rootP;
        else {
            parent[rootQ] = rootP;
            rank[rootP]++;
        }
        count--;
    }

    private void validate(int p) {
        int n = parent.length;
        if (p < 0 || p >= n) {
            throw new IllegalArgumentException("index " + p + " is not between 0 and " + (n-1));
        }
    }

    public int[] parent() {return parent;}
}

Submission Detail

  • 68 / 68 test cases passed.
  • Runtime: 8 ms, faster than 23.72% of Java online submissions for Longest Consecutive Sequence.
  • Memory Usage: 40.8 MB, less than 8.62% of Java online submissions for Longest Consecutive Sequence.

Resources