684. Redundant Connection

/**
 * Using union-find by rank and path compression.
 *
 * Time Complexity Calculations: Total Number of operations=(N). Number of
 * nodes=N Thus time complexity=O(N * alpha(N)) alpha(N) (Also know as
 * Inverse-Ackermann function) grows very slowly and will always be less than or
 * equal to 4.
 *
 * Time Complexity: O(N) Space Complexity : O(N)
 *
 * N = number of edges or the length of edges array.
 */
class Solution {
    public int[] findRedundantConnection(int[][] edges) throws IllegalArgumentException {
        if (edges == null) {
            throw new IllegalArgumentException("Input edges array is null");
        }
        if (edges.length == 0 || edges[0].length == 0) {
            return null;
        }

        UnionFind dsu = new UnionFind(edges.length);
        for (int[] edge : edges) {
            if (!dsu.union(edge[0], edge[1])) {
                return edge;
            }
        }
        return null;
    }

    class UnionFind {
        int[] parent;
        int[] rank;

        UnionFind(int n) {
            parent = new int[n + 1];
            rank = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                parent[i] = i;
            }
        }

        public int findSet(int x) {
            if (x != parent[x]) {
                parent[x] = findSet(parent[x]);
            }
            return parent[x];
        }

        public boolean union(int x, int y) {
            int parentX = findSet(x);
            int parentY = findSet(y);

            if (parentX == parentY) {
                return false;
            }

            if (rank[parentX] >= rank[parentY]) {
                rank[parentX] = rank[parentX] == rank[parentY] ? rank[parentX] + 1 : rank[parentX];
                parent[parentY] = parentX;
            } else {
                parent[parentX] = parentY;
            }

            return true;
        }
    }
}