Solution: Redundant Connection

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

---

Leetcode Problem #684 (Medium): Redundant Connection

---

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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.

---

Examples:

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

Example 2:
Input:	edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output:	[1,4]
Visual:

---

Constraints:

• n == edges.length
• 3 <= n <= 1000
• edges[i].length == 2
• 1 <= ai < bi <= edges.length
• ai != bi
• There are no repeated edges.
• The given graph is connected.

---

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

In this problem, the redundant edge will be the one that links together an already-linked graph. To determine whether already-seen segments of the graph have been connected, we can use a simple union-find (UF) implementation to keep track of the different segments.

With UF, we must define two functions: union and find. The find function will recursively trace a node's lineage back to its ultimate parent and update its value in the parent array (par), providing a shortcut for the next link.

The union function merges two segments by assigning the ultimate parent of one segment to another.

We can iterate through edges and find both vertices of the edge to see if they belong to the same segment. If so, we've located our redundant edge and can return it. If not, we should merge the two different segments with union.

• Time Complexity: O(N) where N is the length of edges
• Space Complexity: O(N) for par and the recursion stack

---

Javascript Code:

(Jump to: Problem Description || Solution Idea)

var findRedundantConnection = function(edges) {
    let par = Array.from({length: edges.length + 1}, (_,i) => i)
    const find = x => x === par[x] ? par[x] : par[x] = find(par[x])
    const union = (x,y) => par[find(y)] = find(x)
    for (let [a,b] of edges)
        if (find(a) === find(b)) return [a,b]
        else union(a,b)
};

---

Python Code:

(Jump to: Problem Description || Solution Idea)

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        par = [i for i in range(len(edges) + 1)]
        def find(x: int) -> int:
            if x != par[x]: par[x] = find(par[x])
            return par[x]
        def union(x: int, y: int) -> None:
            par[find(y)] = find(x)
        for a,b in edges:
            if find(a) == find(b): return [a,b]
            else: union(a,b)

---

Java Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        par = new int[edges.length+1];
        for (int i = 0; i < par.length; i++)
            par[i] = i;
        for (int[] e : edges)
            if (find(e[0]) == find(e[1])) return e;
            else union(e[0],e[1]);
        return edges[0];
    }
    private int[] par;
    private int find(int x) {
        if (x != par[x]) par[x] = find(par[x]);
        return par[x];
    }
    private void union(int x, int y) {
        par[find(y)] = find(x);
    }
}

---

C++ Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        par.resize(edges.size()+1);
        for (int i = 0; i < par.size(); i++)
            par[i] = i;
        for (auto& e : edges)
            if (find(e[0]) == find(e[1])) return e;
            else uniun(e[0],e[1]);
        return edges[0];
    }
private:
    vector<int> par;
    int find(int x) {
        if (x != par[x]) par[x] = find(par[x]);
        return par[x];
    }
    void uniun(int x, int y) {
        par[find(y)] = find(x);
    }
};

Comments

[Timofei Iurov]

we don't have the root so solution is illegal

let/s say we have not [[1,2],[2,3],[3,4],[4,1],[1,5]] but [[4,1],[1,2],[2,3],[3,4],[1,5]] instead

[seanpgallivan]

From the problem description: edges[i] = [ai, bi]
...and from the constraints: 1 <= ai < bi <= edges.length

Your test case is invalid, as [4,1] is a case of ai > bi, violating the constraints.

If you meant [1,4] instead, then the code still works. It doesn't rely on a root, but the instructions state: If there are multiple answers, return the answer that occurs last in the input.

For the case of [[1,2],[2,3],[3,4],[1,4],[1,5]], the code returns the correct answer of [1,4].

For the case of [[1,4],[1,2],[2,3],[3,4],[1,5]], the code returns the correct answer of [3,4].

This is observable directly on leetcode's page for this problem.

[advaitkr]

why you have q[0] in while loop and why not queue.length