Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
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 [ui, vi] that represents a directed edge connecting nodes ui and vi, where ui is a parent of child vi.
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.length3 <= n <= 1000edges[i].length == 21 <= ui, vi <= nui != viProblem summary: 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 [ui, vi] that represents a directed edge connecting nodes ui and vi, where ui is a parent of child vi. 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Union-Find
[[1,2],[1,3],[2,3]]
[[1,2],[2,3],[3,4],[4,1],[1,5]]
redundant-connection)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #685: Redundant Connection II
class Solution {
private int[] p;
public int[] findRedundantDirectedConnection(int[][] edges) {
int n = edges.length;
int[] ind = new int[n];
for (var e : edges) {
++ind[e[1] - 1];
}
List<Integer> dup = new ArrayList<>();
p = new int[n];
for (int i = 0; i < n; ++i) {
if (ind[edges[i][1] - 1] == 2) {
dup.add(i);
}
p[i] = i;
}
if (!dup.isEmpty()) {
for (int i = 0; i < n; ++i) {
if (i == dup.get(1)) {
continue;
}
int pu = find(edges[i][0] - 1);
int pv = find(edges[i][1] - 1);
if (pu == pv) {
return edges[dup.get(0)];
}
p[pu] = pv;
}
return edges[dup.get(1)];
}
for (int i = 0;; ++i) {
int pu = find(edges[i][0] - 1);
int pv = find(edges[i][1] - 1);
if (pu == pv) {
return edges[i];
}
p[pu] = pv;
}
}
private int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
}
// Accepted solution for LeetCode #685: Redundant Connection II
func findRedundantDirectedConnection(edges [][]int) []int {
n := len(edges)
ind := make([]int, n)
for _, e := range edges {
ind[e[1]-1]++
}
dup := []int{}
for i, e := range edges {
if ind[e[1]-1] == 2 {
dup = append(dup, i)
}
}
p := make([]int, n)
for i := range p {
p[i] = i
}
var find func(int) int
find = func(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}
if len(dup) > 0 {
for i, e := range edges {
if i == dup[1] {
continue
}
pu, pv := find(e[0]-1), find(e[1]-1)
if pu == pv {
return edges[dup[0]]
}
p[pu] = pv
}
return edges[dup[1]]
}
for _, e := range edges {
pu, pv := find(e[0]-1), find(e[1]-1)
if pu == pv {
return e
}
p[pu] = pv
}
return nil
}
# Accepted solution for LeetCode #685: Redundant Connection II
class Solution:
def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:
def find(x: int) -> int:
if p[x] != x:
p[x] = find(p[x])
return p[x]
n = len(edges)
ind = [0] * n
for _, v in edges:
ind[v - 1] += 1
dup = [i for i, (_, v) in enumerate(edges) if ind[v - 1] == 2]
p = list(range(n))
if dup:
for i, (u, v) in enumerate(edges):
if i == dup[1]:
continue
pu, pv = find(u - 1), find(v - 1)
if pu == pv:
return edges[dup[0]]
p[pu] = pv
return edges[dup[1]]
for i, (u, v) in enumerate(edges):
pu, pv = find(u - 1), find(v - 1)
if pu == pv:
return edges[i]
p[pu] = pv
// Accepted solution for LeetCode #685: Redundant Connection II
/**
* [0685] Redundant Connection II
*
* 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 [ui, vi] that represents a directed edge connecting nodes ui and vi, where ui is a parent of child vi.
* 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:
* <img alt="" src="https://assets.leetcode.com/uploadisjoint_set/2020/12/20/graph1.jpg" style="width: 222px; height: 222px;" />
* Input: edges = [[1,2],[1,3],[2,3]]
* Output: [2,3]
*
* Example 2:
* <img alt="" src="https://assets.leetcode.com/uploadisjoint_set/2020/12/20/graph2.jpg" style="width: 222px; height: 382px;" />
* 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 <= ui, vi <= n
* ui != vi
*
*/
pub struct Solution {}
// problem: https://leetcode.com/problems/redundant-connection-ii/
// discuss: https://leetcode.com/problems/redundant-connection-ii/discuss/?currentPage=1&orderBy=most_votes&query=
// submission codes start here
impl Solution {
// Credit: https://leetcode.com/problems/redundant-connection-ii/discuss/108058/one-pass-disjoint-set-solution-with-explain
pub fn find_redundant_directed_connection(edges: Vec<Vec<i32>>) -> Vec<i32> {
let n = edges.len();
let mut parents = vec![-1; n + 1];
let mut disjoint_set = vec![0; n + 1];
let mut x1 = -1i32;
let mut x2 = -1i32;
let mut xn = -1i32;
for i in 0..n {
let p = edges[i][0];
let c = edges[i][1];
if parents[c as usize] != -1 {
x1 = parents[c as usize];
x2 = i as i32;
continue;
}
parents[c as usize] = i as i32;
let p1 = Self::dfs_helper(&mut disjoint_set, p);
if p1 == c {
xn = i as i32;
} else {
disjoint_set[c as usize] = p1;
}
}
if xn == -1 {
return edges[x2 as usize].clone();
}
if x2 == -1 {
return edges[xn as usize].clone();
}
edges[x1 as usize].clone()
}
fn dfs_helper(disjoint_set: &mut Vec<i32>, i: i32) -> i32 {
if disjoint_set[i as usize] == 0 {
i
} else {
disjoint_set[i as usize] = Self::dfs_helper(disjoint_set, disjoint_set[i as usize]);
disjoint_set[i as usize]
}
}
}
// submission codes end
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_0685_example_1() {
let edges = vec![vec![1, 2], vec![1, 3], vec![2, 3]];
let result = vec![2, 3];
assert_eq!(Solution::find_redundant_directed_connection(edges), result);
}
#[test]
fn test_0685_example_2() {
let edges = vec![vec![1, 2], vec![2, 3], vec![3, 4], vec![4, 1], vec![1, 5]];
let result = vec![4, 1];
assert_eq!(Solution::find_redundant_directed_connection(edges), result);
}
}
// Accepted solution for LeetCode #685: Redundant Connection II
function findRedundantDirectedConnection(edges: number[][]): number[] {
const n = edges.length;
const ind: number[] = Array(n).fill(0);
for (const [_, v] of edges) {
++ind[v - 1];
}
const dup: number[] = [];
for (let i = 0; i < n; ++i) {
if (ind[edges[i][1] - 1] === 2) {
dup.push(i);
}
}
const p: number[] = Array.from({ length: n }, (_, i) => i);
const find = (x: number): number => {
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;
}
}
Use this to step through a reusable interview workflow for this problem.
Track components with a list or adjacency matrix. Each union operation may need to update all n elements’ component labels, giving O(n) per union. For n union operations total: O(n²). Find is O(1) with direct lookup, but union dominates.
With path compression and union by rank, each find/union operation takes O(α(n)) amortized time, where α is the inverse Ackermann function — effectively constant. Space is O(n) for the parent and rank arrays. For m operations on n elements: O(m × α(n)) total.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.