684. Redundant Connection

At a Glance

Topic: graphs
Pattern: Union-Find
Difficulty: Medium
Companies: Google, Amazon, Microsoft, Apple, Meta
Frequency: High
LeetCode: 684

Problem (one-liner)

Undirected tree on nodes 1..n plus one extra edge. Return the redundant edge (prefer removing later in input if multiple choices — problem guarantees unique answer with tie-break last).

Recognition Cues

Cycle in undirected graph from extra edge
Last edge that closes cycle — Union-Find detects first repeated root merge along processing order

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

DFS cycle detection — heavier bookkeeping.
Union-Find — process edges in order; last edge where find(u)==find(v) — O(n α(n)).

Optimal Solution

Go

type unionFind struct {
	parent []int
}

func newUnionFind(size int) *unionFind {
	parent := make([]int, size+1)
	for index := range parent {
		parent[index] = index
	}
	return &unionFind{parent: parent}
}

func (finder *unionFind) find(node int) int {
	if finder.parent[node] != node {
		finder.parent[node] = finder.find(finder.parent[node])
	}
	return finder.parent[node]
}

func (finder *unionFind) union(left int, right int) bool {
	rootLeft := finder.find(left)
	rootRight := finder.find(right)
	if rootLeft == rootRight {
		return false
	}
	finder.parent[rootRight] = rootLeft
	return true
}

func findRedundantConnection(edges [][]int) []int {
	finder := newUnionFind(len(edges))
	for _, edge := range edges {
		left := edge[0]
		right := edge[1]
		if !finder.union(left, right) {
			return edge
		}
	}
	return []int{}
}

JavaScript

class UnionFind {
  constructor(size) {
    this.parent = Array.from({ length: size + 1 }, (_, index) => index);
  }

  find(node) {
    if (this.parent[node] !== node) {
      this.parent[node] = this.find(this.parent[node]);
    }
    return this.parent[node];
  }

  union(left, right) {
    const rootLeft = this.find(left);
    const rootRight = this.find(right);
    if (rootLeft === rootRight) {
      return false;
    }
    this.parent[rootRight] = rootLeft;
    return true;
  }
}

function findRedundantConnection(edges) {
  const finder = new UnionFind(edges.length);
  for (const edge of edges) {
    const [left, right] = edge;
    if (!finder.union(left, right)) {
      return edge;
    }
  }
  return [];
}