Java Union Find Solution, Simply Explained; Beats 100%.

  • 0

    Using Union-Find Algo, find if the two vertices are in a common set. If so then it's a cycle.
    How Union-Find works: Each vertex in the edges array is a disjoint set initially. When we start traversing through
    the array, we'll check whether both the vertices of an edge are present within a common set. If both vertices are in different set then perform the union of the sets. If the vertices are present in the same set, then we've found a cycle.

    class Solution {
    public int[] findRedundantConnection(int[][] edges) {

        int[] parent = new int[2000]; //create an array of the size>= max value of an integer in 2D array
        for(int i=0;i<parent.length;i++){
            parent[i] = -1;
        for(int i=0;i<edges.length;i++){
            int x = find(parent, edges[i][0]);
            int y = find(parent,edges[i][1]);
                return new int[]{edges[i][0],edges[i][1]};
        return new int[0];
    public int find(int[] parent, int i){
            return i;
        return find(parent, parent[i]);
    public void union(int[] parent, int x, int y){
        int xset = find(parent, x);
        int yset = find(parent, y);
        parent[xset]  = yset;


Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.