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).

Core Basics

Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

Why brute hurts: name the repeated work or state explosion in one sentence.
Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

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

Study Pattern (SDE3+)

0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

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 [];
}