Redundant Connection II

Hard

#0639Time: O(N^2). The main loop runs N times. Inside the loop, the validation function builds an adjacency list and performs a graph traversal, both of which take O(N) time. This results in a total time complexity of O(N * N).Space: O(N), where N is the number of nodes. This space is used for the adjacency list, parent count array, and visited set within the validation function.

Algorithms

Depth-First Search Breadth-First Search Union Find

Data structures

Graph

Prompt

In this problem, a rooted tree is a directed graph such that, there is exactly one node (the root) for which all other nodes are descendants of this node, plus every node has exactly one parent, except for the root node which has no parents.

The given input is a directed graph that started as a rooted tree with n nodes (with distinct values from 1 to n), with one additional directed edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed.

The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u_i, v_i] that represents a directed edge connecting nodes u_i and v_i, where u_i is a parent of child v_i.

Return an edge that can be removed so that the resulting graph is a rooted tree of n nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array.

Example 1:

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

Example 2:

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

Constraints:

n == edges.length
3 <= n <= 1000
edges[i].length == 2
1 <= u_i, v_i <= n
u_i != v_i

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves iterating through each edge, one by one, and checking if its removal results in a valid rooted tree. To satisfy the problem's requirement of returning the last edge in the array in case of multiple possibilities, the iteration is performed in reverse order, from the last edge to the first. The first edge found that validates the tree structure upon removal is the answer.

Algorithm

Iterate through each edge in the edges array, from the last to the first.
For each edge, temporarily remove it from the graph.
Check if the remaining n-1 edges form a valid rooted tree.
A graph is a valid rooted tree if:
1. It has a single root node (a node with an in-degree of 0).
2. All other n-1 nodes have an in-degree of exactly 1.
3. The graph is connected and acyclic. This can be verified by starting a traversal (like BFS or DFS) from the root and ensuring all n nodes are visited exactly once.
The first edge (iterating from the end) whose removal satisfies these conditions is the answer.

Walkthrough

The core of this method is a helper function that validates if a given graph is a rooted tree. This function is called for each potential subgraph formed by removing one edge.

To check if a graph is a valid rooted tree with n nodes and n-1 edges, we verify the following properties:

Parent Uniqueness: We calculate the in-degree for every node. A valid rooted tree must have exactly one node with an in-degree of 0 (the root), and all other n-1 nodes must have an in-degree of 1. If any node has an in-degree greater than 1, or if there isn't exactly one root, the graph is invalid.
Connectivity and Acyclicity: If the parent uniqueness condition holds, we have a potential root. We then perform a graph traversal (like Breadth-First Search or Depth-First Search) starting from this root. If the traversal visits all n nodes exactly once, it confirms the graph is connected and contains no cycles.

The main function iterates from the last edge to the first. For each edge, it constructs a temporary graph excluding that edge and calls the validation logic. The first edge that passes the check is returned.

1class Solution {2    public int[] findRedundantDirectedConnection(int[][] edges) {3        int n = edges.length;4        for (int i = n - 1; i >= 0; i--) {5            if (isTreeAfterRemoval(edges, i, n)) {6                return edges[i];7            }8        }9        return new int[0]; // Should not be reached10    }11 12    private boolean isTreeAfterRemoval(int[][] edges, int edgeToSkip, int n) {13        java.util.List<java.util.List<Integer>> adj = new java.util.ArrayList<>();14        int[] parentCount = new int[n + 1];15        for (int j = 0; j <= n; j++) {16            adj.add(new java.util.ArrayList<>());17        }18 19        for (int j = 0; j < n; j++) {20            if (j == edgeToSkip) continue;21            int u = edges[j][0];22            int v = edges[j][1];23            adj.get(u).add(v);24            parentCount[v]++;25        }26 27        int root = -1;28        for (int j = 1; j <= n; j++) {29            if (parentCount[j] == 0) {30                if (root != -1) return false; // More than one root31                root = j;32            } else if (parentCount[j] > 1) {33                return false; // A node has more than one parent34            }35        }36        if (root == -1) return false; // No root found (implies a cycle)37 38        // Check connectivity from the root39        java.util.Queue<Integer> q = new java.util.LinkedList<>();40        java.util.Set<Integer> visited = new java.util.HashSet<>();41        q.add(root);42        visited.add(root);43        44        while (!q.isEmpty()) {45            int u = q.poll();46            for (int v : adj.get(u)) {47                if (visited.contains(v)) return false; // Cycle detected48                visited.add(v);49                q.add(v);50            }51        }52        53        return visited.size() == n; // All nodes must be reachable54    }55}

Complexity

Time

O(N^2). The main loop runs N times. Inside the loop, the validation function builds an adjacency list and performs a graph traversal, both of which take O(N) time. This results in a total time complexity of O(N * N).

Space

O(N), where N is the number of nodes. This space is used for the adjacency list, parent count array, and visited set within the validation function.

Trade-offs

Pros

Conceptually simple and straightforward to implement.
Guaranteed to find the correct answer due to its exhaustive nature.

Cons

High time complexity of O(N^2), which may be too slow for larger constraints.
Redundant computations, as graph properties are recalculated from scratch in each iteration.

This efficient approach correctly identifies the redundant edge by analyzing the structure of the graph. The addition of an extra edge to a rooted tree can create two types of structural violations: a node having two parents, or the formation of a cycle. This algorithm first checks for a two-parent node. Based on whether one is found, it intelligently uses a Union-Find (Disjoint Set Union) data structure to pinpoint the redundant edge in near-linear time.

Algorithm

Step 1: Detect Two-Parent Node. Iterate through the edges and use a parent array to track the parent of each node. If an edge (u, v) is found where v already has a parent, this indicates v has two parents. Store the two edges leading to v as candidates: cand1 (the first one found) and cand2 (the current one).
Step 2: Handle Cases.
- Case A (No Two-Parent Node): If the first step completes without finding any node with two parents, the graph must contain a cycle. Initialize a Union-Find data structure. Process each edge (u, v) with the union operation. The edge that connects two nodes already in the same set is the one that forms the cycle and is the answer.
- Case B (Two-Parent Node Exists): We have two candidate edges, cand1 and cand2. The goal is to determine which one to remove. We test the graph's integrity by temporarily ignoring cand2. We initialize a Union-Find structure and process all edges except cand2.
  - If a cycle is detected during this process, it means the cycle exists independently of cand2. Therefore, cand1 must be part of that cycle, and removing it is the correct action to fix both the cycle and the two-parent issue. Return cand1.
  - If no cycle is detected, it means removing cand2 is sufficient to make the graph a valid tree (acyclic with correct parent counts). Return cand2.

Walkthrough

The problem can be broken down into three distinct scenarios that our algorithm must handle:

Cycle Only: The added edge creates a cycle, but no node ends up with two parents. This happens when the new edge points to the original root of the tree.
Two Parents, No Cycle: The added edge points to a non-root node, giving it a second parent, but this addition does not create a cycle.
Two Parents and a Cycle: The added edge both creates a cycle and results in a node having two parents.

The algorithm elegantly handles all three cases:

1class Solution {2    public int[] findRedundantDirectedConnection(int[][] edges) {3        int n = edges.length;4        int[] parent = new int[n + 1];5        int[] cand1 = null;6        int[] cand2 = null;7 8        // Step 1: Check for a node with two parents9        for (int[] edge : edges) {10            int u = edge[0];11            int v = edge[1];12            if (parent[v] != 0) {13                cand1 = new int[]{parent[v], v}; // First edge14                cand2 = new int[]{u, v};          // Second edge15                break;16            }17            parent[v] = u;18        }19 20        DSU dsu = new DSU(n);21 22        if (cand1 == null) {23            // Case 1: No node with two parents, so there must be a cycle.24            for (int[] edge : edges) {25                if (!dsu.union(edge[0], edge[1])) {26                    return edge; // This edge forms the cycle27                }28            }29        } else {30            // Case 2 or 3: A node has two parents.31            for (int[] edge : edges) {32                // Skip the second candidate edge to test for a cycle without it33                if (edge[0] == cand2[0] && edge[1] == cand2[1]) {34                    continue;35                }36                if (!dsu.union(edge[0], edge[1])) {37                    // A cycle exists even without cand2, so cand1 must be the culprit.38                    return cand1; // Case 339                }40            }41            // No cycle found without cand2, so removing it is the solution.42            return cand2; // Case 243        }44        45        return new int[0]; // Should not be reached46    }47}48 49class DSU {50    private int[] root;51 52    public DSU(int n) {53        root = new int[n + 1];54        for (int i = 0; i <= n; i++) {55            root[i] = i;56        }57    }58 59    public int find(int i) {60        if (root[i] == i) {61            return i;62        }63        return root[i] = find(root[i]);64    }65 66    public boolean union(int i, int j) {67        int rootI = find(i);68        int rootJ = find(j);69        if (rootI != rootJ) {70            root[rootI] = rootJ;71            return true;72        }73        return false;74    }75}

Complexity

Time

O(N * α(N)), where N is the number of edges and α(N) is the very slow-growing Inverse Ackermann function. For all practical purposes, the complexity is considered linear, O(N).

Space

O(N), where N is the number of nodes. This space is required for the `parent` array used in the initial scan and for the internal array of the Union-Find data structure.

Trade-offs

Pros

Highly efficient with a near-linear time complexity.
Systematically handles all possible scenarios by categorizing the problem.
Avoids expensive graph traversals inside a loop.

Cons

The logic is more complex to understand and implement compared to the brute-force approach.
Requires familiarity with the Union-Find data structure.

Solutions

Solution

1class Solution {2public3  int[] findRedundantDirectedConnection(int[][] edges) {4    int n = edges.length;5    int[] p = new int[n + 1];6    for (int i = 0; i <= n; ++i) {7      p[i] = i;8    }9    UnionFind uf = new UnionFind(n + 1);10    int conflict = -1, cycle = -1;11    for (int i = 0; i < n; ++i) {12      int u = edges[i][0], v = edges[i][1];13      if (p[v] != v) {14        conflict = i;15      } else {16        p[v] = u;17        if (!uf.union(u, v)) {18          cycle = i;19        }20      }21    }22    if (conflict == -1) {23      return edges[cycle];24    }25    int v = edges[conflict][1];26    if (cycle != -1) {27      return new int[]{p[v], v};28    }29    return edges[conflict];30  }31} class UnionFind {32public33  int[] p;34public35  int n;36public37  UnionFind(int n) {38    p = new int[n];39    for (int i = 0; i < n; ++i) {40      p[i] = i;41    }42    this.n = n;43  }44public45  boolean union(int a, int b) {46    int pa = find(a);47    int pb = find(b);48    if (pa == pb) {49      return false;50    }51    p[pa] = pb;52    --n;53    return true;54  }55public56  int find(int x) {57    if (p[x] != x) {58      p[x] = find(p[x]);59    }60    return p[x];61  }62}

1/** * @param {number[][]} edges * @return {number[]} */ var findRedundantDirectedConnection = function ( edges ) { const n = edges . length ; const ind = Array ( n ). fill ( 0 ); for ( const [ _ , v ] of edges ) { ++ ind [ v - 1 ]; } const dup = []; for ( let i = 0 ; i < n ; ++ i ) { if ( ind [ edges [ i ][ 1 ] - 1 ] === 2 ) { dup . push ( i ); } } const p = Array . from ({ length : n }, ( _ , i ) => i ); const find = x => { if ( p [ x ] !== x ) { p [ x ] = find ( p [ x ]); } return p [ x ]; }; if ( dup . length ) { for ( let i = 0 ; i < n ; ++ i ) { if ( i === dup [ 1 ]) { continue ; } const [ pu , pv ] = [ find ( edges [ i ][ 0 ] - 1 ), find ( edges [ i ][ 1 ] - 1 )]; if ( pu === pv ) { return edges [ dup [ 0 ]]; } p [ pu ] = pv ; } return edges [ dup [ 1 ]]; } for ( let i = 0 ; ; ++ i ) { const [ pu , pv ] = [ find ( edges [ i ][ 0 ] - 1 ), find ( edges [ i ][ 1 ] - 1 )]; if ( pu === pv ) { return edges [ i ]; } p [ pu ] = pv ; } };

1class UnionFind { public: vector < int > p ; int n ; UnionFind ( int _n ) : n ( _n ) , p ( _n ) { iota ( p . begin (), p . end (), 0 ); } bool unite ( int a , int b ) { int pa = find ( a ), pb = find ( b ); if ( pa == pb ) return false ; p [ pa ] = pb ; -- n ; return true ; } int find ( int x ) { if ( p [ x ] != x ) p [ x ] = find ( p [ x ]); return p [ x ]; } }; class Solution { public: vector < int > findRedundantDirectedConnection ( vector < vector < int >>& edges ) { int n = edges . size (); vector < int > p ( n + 1 ); for ( int i = 0 ; i <= n ; ++ i ) p [ i ] = i ; UnionFind uf ( n + 1 ); int conflict = - 1 , cycle = - 1 ; for ( int i = 0 ; i < n ; ++ i ) { int u = edges [ i ][ 0 ], v = edges [ i ][ 1 ]; if ( p [ v ] != v ) conflict = i ; else { p [ v ] = u ; if ( ! uf . unite ( u , v )) cycle = i ; } } if ( conflict == - 1 ) return edges [ cycle ]; int v = edges [ conflict ][ 1 ]; if ( cycle != - 1 ) return { p [ v ], v }; return edges [ conflict ]; } };

1class UnionFind : def __init__ ( self , n ): self . p = list ( range ( n )) self . n = n def union ( self , a , b ): if self . find ( a ) == self . find ( b ): return False self . p [ self . find ( a )] = self . find ( b ) self . n -= 1 return True def find ( self , x ): if self . p [ x ] != x : self . p [ x ] = self . find ( self . p [ x ]) return self . p [ x ] class Solution : def findRedundantDirectedConnection ( self , edges : List [ List [ int ]]) -> List [ int ]: n = len ( edges ) p = list ( range ( n + 1 )) uf = UnionFind ( n + 1 ) conflict = cycle = None for i , ( u , v ) in enumerate ( edges ): if p [ v ] != v : conflict = i else : p [ v ] = u if not uf . union ( u , v ): cycle = i if conflict is None : return edges [ cycle ] v = edges [ conflict ][ 1 ] if cycle is not None : return [ p [ v ], v ] return edges [ conflict ]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem