684. Redundant Connection 🚀

---

Solution Developed In:

The Question

For this article we will be covering Leetcode's '684. Redundant Connection' question. Knowing how to solve this problem with UnionFind will be vital to solving 1584. Min Cost to Connect All Points' with Kruskal's Algorithm.

Question:

In this problem, a tree is an undirected graph that is connected and has no cycles.
You are given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The graph is represented as an array edges of length n where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the graph.
Return an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input.

Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]

Explaining The Question

This Question is rated Medium. Which is for the most part accurate. This question is kinda of a trick question, if you're like me you'll probably think 'Greedy Depth First Search on all nodes until we find out last loop'. Which works, but is not the best way to solve this problem.

What's expected of you is to use Union Find to solve this problem. Specifically, Union Find by Rank is expected.

This question is only Medium if you know how to use Union Find with Union Find by Rank.

We have been given a list of Nodes and Edges ([Node -> Edge]). Which forms a Graph, we need to find the Redundant Edge. Which is the last connection between two nodes that forms a Cycle.

---

Recommended Knowledge

1. Graph Theory
2. Union Find
3. Union Find by Rank
4. Path Compression
5. Amortized Analysis

What do we know?

1. We have a 2D Array of '1's and '0's.
2. It's a M x N Matrix
3. Neighbors are left, right, top, and bottom.
4. We need to find the max area of an island. Meaning, the number of cells in the island.

How we're going to do it:

We're going to find this Redundant Edge by using a Union Find data structure. We'll be creating a Tree from the provided Node & Edge array. The reasons this will work is because within a tree, there are no cycles. So when we're creating the tree, we'll be checking if the 2 given nodes have the same parent. What that mean's their was an attempt to create a connection in what was once a perfect tree.

Once we detect that attempted connection, we can identify the Node Edge that would've created a redundant connection.

1. We're going to firstly define our Ranks and Parents. A rank is the number of nodes that tree has. A parent is the node that is the parent of the current node. With this information, we know the size and structure of the tree.
2. We're going to define our Find() function. When we're Unioning two nodes, we need to find the parents of the given node. We implement this function by asking the parents array, 'Who this nodes parent?' and we keep asking this question until the parent of a node is itself (Meaning, it's the root). We also implement a Path Compression technique to speed up this process to achieve an Amortized O(1) time complexity.
3. We're going to define our Union() function. The purpose of this function is to merge 2 trees together. Firstly, we need to Find() the root nodes of the 2 supplied nodes. We check if they're of the same parent, meaning it's a redundant connection and we need to stop execution. If they're not, we need to merge the 2 trees. We do this by setting the parent of the 2 nodes to the same parent. As well as updating their ranks
4. Now we have all of our functions for a UnionFind structure, we will now attempt to Union all the supplied nodes. If at any point our Union connection returns false (Found a redundant connection), we can stop execution and return that edge.

Big O Notation:

• Time Complexity: O(V * E) / O(n) | Where n is the number of nodes in the Graph. As we're going to visit every node in the matrix. Where V is the number of nodes in the graph and E is the number of edges in the graph. As in the worst case, the last node will attempt a redundant connection.

• Space Complexity: O(h) | Where h is the largest number of nodes within our graph. As we're going to create a tree from the graph. Which will be the same as the number of nodes in the graph.

We did although implemented a Path Compression and Union by Rank technique to achieve a Amortized O(1) time complexity on our Union and Find functions. But as we will still need to iterate through the Nodes, we will still have a O(n) time complexity.

Leetcode Results:

See Submission Link:

• Runtime: 78 ms, faster than 85.83% of JavaScript online submissions for Max Area of Island
• Memory Usage: 45.1 MB, less than 67.24% of JavaScript online submissions for Max Area of Island.

---

The Solution

class UnionFind {

    /**
     * @summary We're going to generate a UnionFind data structure.
     * Union Find is a special data-structure that can be used to form
     * a disjoint set (A tree). For this solution, we're going to use
     * the Rank variant of Union Find. All this mean's is that we keep
     * track the number of nodes a given tree has. It allows us to merge
     * trees that will require the minimal amount of work (Increases
     * the Amortized Complexity).
     *
     * @param  {Array} edges [[node, edge_to_connect_to], [node, edge_to_connect_to]]
     */
    constructor(edges) {

        // Create a array of Ranks (Index -> Tree Size)
        // Looks Like: [1,1,1,1]
        // (Each node is a tree of size 1 by default)
        this.ranks = new Array(edges.length).fill(1);

        // Create a array of Parents (Index -> Index of Parent)
        // If we keep following the parent, we'll eventually find
        // the root of the tree.
        // Looks Like: [0,1,2,3]
        // (Each node's parent is itself by default, as it's the root of it's tree)
        this.parents = Array.from(Array(edges.length).keys());
    }

    /**
     * @summary Find the root of a given node, we do this by asking the parents
     * list 'Who's the parent of this node's index?', we repeat this until the parent
     * of the node is itself. Meaning, we have reached the root of the tree.
     * We have also utilized a concept called 'Path Compression'. This mean's
     * instead of going up the tree one node at a time, we go up the tree 2 nodes
     * at a time. Tree height should be very small due to the 'rank' concept.
     *
     * Time Complexity: Amortized O(1) (Best, tree height is small)
       *              : O(log n) (Average)
       *              : O(n) (Worst, linked list tree)
     *
     * Space Complexity: O(1) (Finding allocated no space)
     *
     * Technically, we rate an algorithm by it's worst case. Thus this is
     * O(n) in time. But it's such a rare case that we don't care, so it's better
     * to use the amortized case of O(1)
     *
     * @param  {Number} index (Index of node in [Parents, Ranks, Edges])
     * @return {Number}       (Index of parent, the root node of the tree)
     */
    find(index) {
        // Get parent of node
        let parent = this.parents[index];

        // Keep getting parents until we reach the root of the tree
        while (parent != this.parents[parent]) {
            // Path Compression
            parent = this.parents[this.parents[parent]];
        }
        return parent;
    }

    /**
     * @summary Merge two trees by connecting the root of the  tree by rank.
     * What this mean's, is we're going to find the parents of both of the supplied
     * nodes, and then figure out which tree is larger. We then connect the root of
     * the smaller tree to the root of the larger tree.
     * Why? Because, during the Find() operation, we want to reduce the number of
     * steps required to get to the root of a given tree. By merging smaller into larger
     * we won't need as many steps to find the root of a given parent.
     *
     * This is called Union by Rank. Rank meaning, size of a given tree. When you combine
     * Path Compression and Union by Rank, you get a amortized O(1) time complexity.
     *
     * Time and Space Complexity is the same as Find() as we utilise that function.
     *
     * @param  {Number} n1 (Index of node 1)
     * @param  {Number} n2 (Index of node 2)
     * @return {Boolean}   (False if nodes are already in the same tree)
     */
    union(n1, n2) {

        // Find the parents of each node.
        const n1_parent = this.find(n1);
        const n2_parent = this.find(n2);

        // Are the nodes already in the same tree?
        // REDUNDANT CONNECTION!!!
        if (n1_parent === n2_parent) return false;

        // Union by rank, merge smallest into largest.
        if (this.ranks[n1_parent] > this.ranks[n2_parent]) {
            // Update parent and ranks
            this.parents[n2_parent]  = n1_parent;
            this.ranks  [n2_parent] += this.ranks[n1_parent];
        } else {
            // Merge n1 into n2
            this.parents[n1_parent]  = n2_parent;
            this.ranks  [n1_parent] += this.ranks[n2_parent];
        }

        // Successfully merged. Ranks and parents updated
        return true;
    }
}

/**
 * @param {number[][]} edges
 * @return {number[]}
 */
var findRedundantConnection = function (edges) {
    // The basic premise of this solution is
    // to use UnionFind to find the redundant edge.
    // UnionFind will attempt to create a tree by merging nodes
    // together. If at any point, two nodes are already connected,
    // meaning, they're in the same tree, we have found the redundant connection.

    // We're going to initialize a Union Find data structure
    // so we can attempt to build our tree.
    const Union_Find = new UnionFind(edges);

    // Let's build our tree.
    // Union each node and their edges together.
    // If at any point, a node and edge are already in the same Tree.
    // END loop, we found the redundant connection.
    for (const [node, edge] of edges) {
        if (!Union_Find.union(node, edge)) return [node, edge];
    }
};