Redundant Connection II

Hard
1524.

Redundant Connection II

Redundant Connection II is a hard coding problem on depth-first search, graph and union find, asked in Amazon, Google and Uber interviews.

A rooted tree is a directed graph with one root node that every other node descends from; every node except the root has exactly one parent, and the root has none.

The CodeKairo mentorship chart started as a rooted tree on n people labelled 1 to n, with each edge [u, v] meaning u mentors v. Then one extra directed edge was added between two different people; it was not already in the chart. You receive the resulting n edges as edges.

Return an edge whose removal turns the graph back into a rooted tree on all n nodes. If several edges qualify, return the one that appears last in edges.

Example 1

Input
edges = [[1,2],[1,3],[3,2]]
Output
[3,2]
Explanation
Node 2 has two parents; dropping the later edge `[3,2]` leaves the tree rooted at 1.

Example 2

Input
edges = [[2,3],[3,1],[1,4],[4,2]]
Output
[4,2]
Explanation
No node has two parents, but the four edges form a cycle. Removing any cycle edge works; `[4,2]` is the last one listed.

Example 3

Input
edges = [[3,1],[1,2],[2,3],[4,2]]
Output
[1,2]
Explanation
Node 2 has parents 1 and 4, and 3 → 1 → 2 → 3 is a cycle. Only removing `[1,2]` leaves a tree (rooted at 4).

Constraints

  • n == edges.length
  • 3 <= n <= 1000
  • edges[i].length == 2
  • 1 <= ui, vi <= n
  • ui != vi
  • the input is a rooted tree plus one extra edge
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} edges
 * @return {number[]}
 */
var findRedundantDirectedConnection = function(edges) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Redundant Connection II — Solution in Python, Java & C++

Redundant Connection II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Redundant Connection II is a hard coding problem on depth-first search, graph and union find, asked in Amazon, Google and Uber interviews.

Problem statement

A rooted tree is a directed graph with one root node that every other node descends from; every node except the root has exactly one parent, and the root has none.

The CodeKairo mentorship chart started as a rooted tree on n people labelled 1 to n, with each edge [u, v] meaning u mentors v. Then one extra directed edge was added between two different people; it was not already in the chart. You receive the resulting n edges as edges.

Return an edge whose removal turns the graph back into a rooted tree on all n nodes. If several edges qualify, return the one that appears last in edges.

Example 1

Input: edges = [[1,2],[1,3],[3,2]]
Output: [3,2]
Explanation: Node 2 has two parents; dropping the later edge `[3,2]` leaves the tree rooted at 1.

Example 2

Input: edges = [[2,3],[3,1],[1,4],[4,2]]
Output: [4,2]
Explanation: No node has two parents, but the four edges form a cycle. Removing any cycle edge works; `[4,2]` is the last one listed.

Example 3

Input: edges = [[3,1],[1,2],[2,3],[4,2]]
Output: [1,2]
Explanation: Node 2 has parents 1 and 4, and 3 → 1 → 2 → 3 is a cycle. Only removing `[1,2]` leaves a tree (rooted at 4).

Constraints

  • n == edges.length
  • 3 <= n <= 1000
  • edges[i].length == 2
  • 1 <= ui, vi <= n
  • ui != vi
  • the input is a rooted tree plus one extra edge

Hints for Redundant Connection II

  1. Hint 1

    Adding one directed edge to a rooted tree can break it in two ways: some node gets a second parent, or a cycle appears — or both at once.

  2. Hint 2

    If a node has two parents, the answer is one of its two incoming edges. Which one? Try leaving the later one out and see whether a cycle remains.

  3. Hint 3

    Union-find over the edges (skipping the second incoming edge, if any) detects the cycle. A cycle left over means the first incoming edge was the culprit; no cycle means the second one was; no double parent means the edge that closes the cycle.

How to solve Redundant Connection II

The extra edge either gives some node a second parent, closes a cycle, or does both. Spotting the double parent first narrows the answer to two candidates, and a union-find pass decides between them.

Approach

  1. Scan the edges, recording each node's first parent. If an edge [u, v] arrives for a v that already has a parent, remember the earlier edge as cand1 and this edge as cand2.
  2. Run union-find over the edges in order, skipping cand2 if it exists.
  3. If some edge [u, v] joins two nodes already in the same set, a cycle exists: return cand1 if there was a double parent, otherwise return [u, v].
  4. If the pass finishes without a cycle, return cand2.

Why it works

With a double parent, exactly one of the two incoming edges must go. Skipping cand2: if the remaining graph still has a cycle, cand2 cannot be the fix, so cand1 (which lies on that cycle) is; if no cycle remains, removing cand2 already yields a tree, and since cand2 comes later it is the required answer. Without a double parent, the extra edge points at the root and closes a cycle; removing any cycle edge leaves a tree, and union-find reports exactly the cycle edge that appears last in the list, because the earlier cycle edges only form a path.

Complexity

  • Time — O(n · α(n))
  • Space — O(n)

Pitfalls

  • Union-find alone fails when a node has two parents but the cycle is closed by a different edge — the double-parent check must come first.
  • When both candidates would produce a tree, the later one (cand2) must be returned.
  • Union by undirected connectivity is enough for cycle detection here; no direction-aware traversal is needed.

Reference solution

Python

from typing import List

def findRedundantDirectedConnection(edges: List[List[int]]) -> List[int]:
    n = len(edges)
    parent = [0] * (n + 1)
    cand1 = None
    cand2 = None
    for u, v in edges:
        if parent[v] != 0:
            cand1 = [parent[v], v]
            cand2 = [u, v]
        else:
            parent[v] = u
    root = list(range(n + 1))

    def find(x):
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

    for u, v in edges:
        if cand2 is not None and u == cand2[0] and v == cand2[1]:
            continue
        ru, rv = find(u), find(v)
        if ru == rv:
            return cand1 if cand1 is not None else [u, v]
        root[rv] = ru
    return cand2

Java

public static int[] findRedundantDirectedConnection(int[][] edges) {
    int n = edges.length;
    int[] parent = new int[n + 1];
    int[] root = new int[n + 1];
    for (int k = 0; k <= n; k++) root[k] = k;
    int[] cand1 = null, cand2 = null;
    for (int[] e : edges) {
        if (parent[e[1]] != 0) { cand1 = new int[]{parent[e[1]], e[1]}; cand2 = new int[]{e[0], e[1]}; }
        else parent[e[1]] = e[0];
    }
    for (int[] e : edges) {
        if (cand2 != null && e[0] == cand2[0] && e[1] == cand2[1]) continue;
        int ra = rcFind(root, e[0]), rb = rcFind(root, e[1]);
        if (ra == rb) return cand1 != null ? cand1 : new int[]{e[0], e[1]};
        root[rb] = ra;
    }
    return cand2;
}

static int rcFind(int[] root, int x) {
    while (root[x] != x) { root[x] = root[root[x]]; x = root[x]; }
    return x;
}

C++

static int rcFind(vector<int>& root, int x) {
    while (root[x] != x) { root[x] = root[root[x]]; x = root[x]; }
    return x;
}

vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
    int n = edges.size();
    vector<int> parent(n + 1, 0), root(n + 1);
    for (int k = 0; k <= n; k++) root[k] = k;
    vector<int> cand1, cand2;
    for (auto& e : edges) {
        if (parent[e[1]] != 0) { cand1 = {parent[e[1]], e[1]}; cand2 = {e[0], e[1]}; }
        else parent[e[1]] = e[0];
    }
    for (auto& e : edges) {
        if (!cand2.empty() && e[0] == cand2[0] && e[1] == cand2[1]) continue;
        int ra = rcFind(root, e[0]), rb = rcFind(root, e[1]);
        if (ra == rb) return !cand1.empty() ? cand1 : vector<int>{e[0], e[1]};
        root[rb] = ra;
    }
    return cand2;
}

JavaScript

var findRedundantDirectedConnection = function(edges) {
    var n = edges.length;
    var parent = [], root = [];
    for (var k = 0; k <= n; k++) { parent.push(0); root.push(k); }
    var cand1 = null, cand2 = null;
    for (var i = 0; i < n; i++) {
        var u = edges[i][0], v = edges[i][1];
        if (parent[v] !== 0) { cand1 = [parent[v], v]; cand2 = [u, v]; }
        else parent[v] = u;
    }
    var find = function(x) {
        while (root[x] !== x) { root[x] = root[root[x]]; x = root[x]; }
        return x;
    };
    for (var j = 0; j < n; j++) {
        var a = edges[j][0], b = edges[j][1];
        if (cand2 !== null && a === cand2[0] && b === cand2[1]) continue;
        var ra = find(a), rb = find(b);
        if (ra === rb) return cand1 !== null ? cand1 : [a, b];
        root[rb] = ra;
    }
    return cand2;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Graph Data Structure