What is the brute force approach and complexity for Redundant Connection?

Remove edges from last to first; the first removal that leaves a connected graph is the answer with time complexity O(N²) and space complexity O(N).

What is the optimal approach and complexity for Redundant Connection?

Union the edges in input order; the first edge whose ends already share a root is the answer with optimal time complexity O(N · α(N)) and space complexity O(N).

How do you identify the pattern for Redundant Connection?

Look for key signals in the prompt: "a tree with one extra edge" indicates `n` nodes and `n` edges means exactly one cycle, and that cycle is what we are after.; "remove an edge so it is a tree again" indicates Find the edge that closes the cycle: its two ends are already joined.; "the one that occurs last in the input" indicates Read the input in order and stop at the first edge that closes a cycle..

Redundant Connection

Medium·LeetCode #684 Pro OnlyBasic Reinforcement

LeetCode

Problem Statement

A tree is a connected graph with no cycle. Here you get a tree with one extra edge added: n nodes labelled 1 to n, and exactly n edges, so the graph has exactly one cycle.

Return an edge that you can remove so that the rest is still a tree. If more than one edge works, return the one that comes last in the input.

Input

edges: a list of n pairs [a, b], one per edge, with n = edges.length.

Output

One pair [a, b] from edges: the edge to remove.

Example 1

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

Output: [2, 3]

1–2, 1–3 and 2–3 form a triangle. Removing 1–2 or 1–3 also leaves a tree, but 2–3 comes last in the input.

Example 2

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

Output: [1, 4]

The cycle is 1–2–3–4–1. Removing 1–2, 2–3 or 3–4 also works, but 1–4 is the last edge of the cycle in the input. Edge 1–5 is not on the cycle.

Constraints

• n == edges.length
• 3 ≤ n ≤ 1000
• 1 ≤ aᵢ < bᵢ ≤ n
• There are no repeated edges.
• The given graph is connected.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“a tree with one extra edge”

→ `n` nodes and `n` edges means exactly one cycle, and that cycle is what we are after.

“remove an edge so it is a tree again”

→ Find the edge that closes the cycle: its two ends are already joined.

“the one that occurs last in the input”

→ Read the input in order and stop at the first edge that closes a cycle.

Approach Complexity Ladder

Brute Force — drop edges from the last oneO(N²)O(N)

Remove edges from last to first; the first removal that leaves a connected graph is the answer

Optimal — Union-Find: the first edge that fails to unionO(N · α(N))O(N)

Union the edges in input order; the first edge whose ends already share a root is the answer

Brute Force Intuition

Remove one edge at a time, starting from the last edge in the input. After a removal, n − 1 edges remain. Search from node 1: if all n nodes are still reached, what remains is a tree, so the first removal that keeps every node connected is the answer.

Recognition rule for this sub-pattern:

If both ends of an edge already share a root, this edge closes a cycle.

Remember this · Union-Find (DSU)

Trigger

Edges arrive one by one, "are these connected?", merge equivalent items, count components, extra edge creating a cycle.

Think

Am I repeatedly merging groups and asking whether two things are in the same group?

Key question

What are the elements, and what does it mean to union two of them?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Union-Find (DSU) translate into production architectures and low-level memory mechanics.

LLD Architecture