Coding Interview PatternsRedundant Connection II
HardUnion Find

Redundant Connection II

Explanation & Solution

Practice Problem

Description

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 the root 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.

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.

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

Output:[2,3]
0
2
1
3

Explanation: Node 3 has two parents (1 and 2). Removing [2,3] results in a valid rooted tree.

Constraints

  • n == edges.length
  • 3 <= n <= 1000
  • edges[i].length == 2
  • 1 <= ui, vi <= n
  • ui != vi

Approach

Union Find pattern

1. Detect Node with Two Parents

  • Scan edges for a node with in-degree 2
  • If found, the two edges pointing to this node are cand1 (earlier) and cand2 (later)
  • One of these must be removed

2. Case 1: No Node with Two Parents

  • The extra edge creates a cycle without any node having two parents
  • Use Union Find to detect the cycle — the edge that causes find(u) === find(v) is the answer

3. Case 2: Node Has Two Parents

  • Tentatively remove cand2 (the later edge) and build the tree with Union Find
  • If no cycle is found → cand2 is the answer
  • If a cycle is found → cand1 is the answer (cand2 wasn't the problem)

Key Insight

  • A directed graph that was a rooted tree + 1 edge has exactly one of two issues: a cycle, or a node with two parents (or both)
  • By checking for double parents first and then using Union Find for cycle detection, we cover all cases
Time
**O(n · α(n))** ≈ **O(n)**
Space
O(n)

Visualization

Input:
BFS Traversal4 nodes, 3 edges
0123
output—

Press play to start bfs traversal

CurrentQueuedVisited
4 steps

Solution Code

Previous
Regions Cut by Slashes
Next
Number of Islands II