684 Redundant Connection

Techniques Used

• Union Find
• Graph

Approach

• This problem can be simplified as: you are required to find the first edge which when processed by our union-find algorithm will create a cycle in the graph. Just return that edge.

Time Complexity

• Time Complexity: O(NlogN) Union will take (in worst case) : O(logN) time. Find operation is almost O(1) due to path compression.
• Space Complexity: O(N)

Code: Java

class Solution {


    static int[] parent;
    static int[] rank;


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

        int n = edges.length;
        parent = new int[n + 1];
        rank = new int[n + 1];

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

        for(int i = 0; i < edges.length; i++){

            boolean temp = union(edges[i][0], edges[i][1]);
            if(temp == false) return new int[]{edges[i][0], edges[i][1]};

        }

        return new int[]{-1, -1};

    }

    public int find(int x) {
        if (parent[x] == x)
            return x;
        return find(parent[x]); // find the parent of x

    }
    public boolean union(int x, int y) {
        int lx = find(x); // parent of x
        int ly = find(y); // parent of y
        if (lx != ly) {
            if (rank[lx] > rank[ly]) { //a parent having higher rank (bigger tree) will be preferred
                parent[ly] = lx;
            } else if (rank[ly] > rank[lx]) {
                parent[lx] = ly;
            } else {
                parent[lx] = ly;
                rank[ly]++;
            }
            return true;
        } else {
            return false; // parents are same, already connected
        }
    }
}