Skip to content

Volume ITechnology

4.20.10 — Redundant Connection ​

LeetCode 684 · Medium

The problem ​

Start with a tree of n nodes and n − 1 edges, then add one extra edge. Return the edge that can be removed to make it a tree again. If several would work, return the one that appears last in the input.

edges = [[1,2],[1,3],[2,3]]   →  [2,3]

The pattern ​

A tree with n nodes has exactly n − 1 edges and no cycles. Adding one edge creates exactly one cycle, and the redundant edge is any edge on that cycle.

Process the edges in order. For each one, ask:

Are these two nodes already connected?

If not, this edge joins two separate groups — keep it. If they already are, this edge closes a cycle, and since you are processing in order, it is the last edge that could have done so. Return it.

"Are these two connected, given edges arriving one at a time" is precisely what union-find answers.

Union-find in three lines of idea ​

Each group has a representative. find(x) walks up to x's representative; union(a, b) makes one representative point at the other, merging the groups.

Two nodes are in the same group exactly when find(a) == find(b).

Two optimisations make it effectively constant time, and both are one line:

Path compression — while walking up in find, point each node directly at the representative, so the next walk is instant.

Union by size — always attach the smaller tree under the larger one, so the trees stay shallow.

With both, each operation costs O(\alpha(n)), where \alpha is the inverse Ackermann function. It is below 5 for any input that fits in the universe, so treat it as constant — and say it that way rather than claiming exactly O(1).

The solution ​

python
class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        n = len(edges)
        parent = list(range(n + 1))          # (1) nodes are 1-indexed
        size = [1] * (n + 1)  # (2)

        def find(x: int) -> int:  # (3)
            while parent[x] != x:  # (4)
                parent[x] = parent[parent[x]]     # (5) path compression
                x = parent[x]
            return x  # (6)

        def union(a: int, b: int) -> bool:  # (7)
            ra, rb = find(a), find(b)
            if ra == rb:  # (8)
                return False                      # already connected → a cycle
            if size[ra] < size[rb]:  # (9)
                ra, rb = rb, ra                   # attach smaller under larger
            parent[rb] = ra  # (10)
            size[ra] += size[rb]
            return True

        for a, b in edges:  # (11)
            if not union(a, b):  # (12)
                return [a, b]

        return []
ts
function findRedundantConnection(edges: number[][]): number[] {
  const n = edges.length;
  const parent = Array.from({ length: n + 1 }, (_, i) => i);  // (1)
  const size = new Array(n + 1).fill(1);  // (2)

  function find(x: number): number {  // (3)
    while (parent[x] !== x) {  // (4)
      parent[x] = parent[parent[x]];  // (5)
      x = parent[x];
    }
    return x;  // (6)
  }

  function union(a: number, b: number): boolean {  // (7)
    let ra = find(a), rb = find(b);
    if (ra === rb) return false;  // (8)
    if (size[ra] < size[rb]) [ra, rb] = [rb, ra];  // (9)
    parent[rb] = ra;  // (10)
    size[ra] += size[rb];
    return true;
  }

  for (const [a, b] of edges) {  // (11)
    if (!union(a, b)) return [a, b];  // (12)
  }

  return [];
}

parent[x] = parent[parent[x]] is path halving, a one-line version of path compression that points each node at its grandparent as you climb. It is nearly as effective as the full two-pass version and much shorter.

union returns False when the nodes were already connected, which is exactly the cycle signal. Returning a boolean from union rather than checking find separately keeps the loop to one line.

Processing edges in input order is what satisfies "return the last one that could be removed". The first edge that closes a cycle is the last removable one, because every earlier edge was needed to build up the components.

n + 1 slots because nodes are numbered from 1. Off-by-one here is a silent index error.

Line by line ​

(1) parent[x] is the node that x points to. Each group of connected nodes forms a little tree, and the node at the top of the tree, which points to itself, is the group's root. At the start, every node points to itself, so every node is its own group. The list has n + 1 slots because the nodes are numbered from 1, not 0.

(2) size[r] is how many nodes are in the group whose root is r.

(3) find(x) returns the root of x's group. Two nodes are in the same group exactly when they have the same root.

(4) Climb until we reach a node that points to itself.

(5) On the way, make each node point to its grandparent. This shortcut is called path compression. It makes the trees flatter every time find runs, so later climbs are shorter.

(6) The root.

(7) union(a, b) joins the groups of a and b. It returns False if they were already in the same group.

(8) Same root, so a and b are already connected. Adding an edge between them would close a loop. That is the edge the problem asks for.

(9) Put the smaller group under the bigger one. This keeps the trees short. Together with line (5), it makes each find almost constant time.

(10) Join the two groups, and add the smaller group's size to the bigger one's.

(11) Add the edges one by one, in the order given.

(12) The first edge that joins two already-connected nodes is the extra edge. Because we go in order, it is also the last such edge in the list, which is what the problem wants when several answers are possible.

Trace ​

[[1,2],[1,3],[2,3]]

edgefind(a)find(b)action
[1,2]12different → union, groups {1,2}
[1,3]13different → union, groups {1,2,3}
[2,3]11same → cycle → return [2,3]

A picture of union-find ​

Imagine people showing up to a party. Every person is initially their own "boss". When edge [1,2] arrives, person 1 and person 2 become friends. We assign one to be the "boss" of the friend group. (Let's say 1 is the boss of 2). When [1,3] arrives, we check: Who is 1's boss? (1). Who is 3's boss? (3). They have different bosses, meaning they weren't in the same friend group. Now they merge. 3 accepts 1 as the boss. When [2,3] arrives, we check: Who is 2's boss? (1). Who is 3's boss? (1). They already have the same boss! This means they are already in the same friend group. Making them friends doesn't connect anyone new; it just creates a redundant connection (a circle).

Edge cases ​

  • The extra edge closes a loop of three, like edges 1–2, 2–3, 1–3. The third edge finds 1 and 3 already joined.
  • Several edges could be removed. The problem wants the one that appears last. Adding edges in order and returning the first that closes a loop gives exactly that, because every earlier edge was needed to build the tree.

Complexity ​

O(n \cdot \alpha(n)), effectively O(n). O(n) space. To break it down: we process each of the N edges exactly once. For each edge, we do a find and possibly a union. Thanks to path compression and union by size, the find operation climbs a maximally flattened tree. The inverse Ackermann function \alpha(n) is a mathematical function that grows so slowly it is \le 5 for any realistic input size. Thus, each edge takes effectively O(1) time, yielding O(N) overall time. The parent and size arrays each take exactly N+1 slots, giving O(N) space.

Why not DFS? ​

You could, for each edge, remove it and check whether the graph is still connected — O(n^2). Or DFS from scratch to find the cycle and then pick the last of its edges from the input, which is O(n) but fiddlier.

Union-find is the right tool because the edges arrive one at a time and the question is asked after each one. That is the exact situation it is built for, and it is the distinction worth carrying:

  • All the edges up front, one query → DFS or BFS is simpler.
  • Edges arriving, connectivity asked repeatedly → union-find.

Where this goes next ​

  • Number of Connected Components — union everything, then count the distinct representatives. 4.20.11.
  • Graph Valid Tree — connected and exactly n − 1 edges. 4.20.12.
  • Kruskal's minimum spanning tree — sort the edges by weight and add each one whose endpoints are not already connected. That "already connected?" check is this union returning False. 4.21.
  • Accounts Merge, Number of Islands II, Most Stones Removed — all union-find.

Redundant Connection II (LeetCode 685) is the directed version, and it is much harder. The extra edge may create a node with two parents, a cycle, or both, and the three cases need separate handling. Know that it exists.

What the interviewer will push on ​

"Why union-find rather than DFS?" Edges arrive one at a time and connectivity is queried after each.

"What is the complexity of union-find?" O(\alpha(n)) amortized with both optimisations, effectively constant. Say "effectively", not "exactly".

"What are the two optimisations and what does each fix?" Path compression flattens the tree during find; union by size stops a tall tree forming during union. Without both, the worst case is O(n) per operation.

"Why does returning the first cycle-closing edge give the last removable one?" Every earlier edge was needed to build the components, so the first one to close a cycle is the last one that can be dropped.

"What if the graph were directed?" A different problem — Redundant Connection II, with three cases.

One thing to volunteer: state the tree fact first. "A tree has n − 1 edges and no cycle, so one extra edge creates exactly one cycle, and any edge on it is removable." That framing makes the union-find choice obvious.

Next: 4.20.11 Number of Connected Components — union-find in its simplest form.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet