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

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

What is the optimal approach and complexity for Redundant Connection II?

Find a node with two parents (A, B); union every edge except B; a cycle left means drop A, otherwise drop B with optimal time complexity O(N · α(N)) and space complexity O(N).

How do you identify the pattern for Redundant Connection II?

Look for key signals in the prompt: "directed edges" indicates Arrows matter: each node should have one parent, and a node with two parents is a special case.; "rooted tree with one extra edge" indicates Either one node has two parents, or the extra arrow makes a directed cycle.; "the one that occurs last in the input" indicates Among the valid choices, the last arrow in the input wins, so read the input in order..

Redundant Connection II

Hard·LeetCode #685 Pro OnlyMedium

LeetCode

Problem Statement

You get n directed edges [u, v] (an arrow from u to v) on nodes 1 to n. Before one extra arrow was added, the arrows formed a rooted tree: one root that no arrow points into, and every other node has exactly one incoming arrow (its parent), with a path from the root to every node.

Return one arrow that you can remove so that what remains is a rooted tree again. If more than one arrow works, return the one that comes last in the input.

Input

edges: n pairs [u, v], one per arrow, with n = edges.length.

Output

One pair [u, v] from edges: the arrow to remove.

Example 1

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

Output: [2, 3]

Node 3 has two parents, 1 and 2. Removing 1 → 3 leaves 1 → 2 → 3, a rooted tree. Removing 2 → 3 leaves 1 → 2 and 1 → 3, also a rooted tree. Both work, and 2 → 3 comes later in the input.

Example 2

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

Output: [4, 1]

No node has two parents, but the arrows 1 → 2 → 3 → 4 → 1 form a cycle, and node 5 hangs off node 1. Removing any cycle arrow leaves a rooted tree. The last one in the input is 4 → 1.

Constraints

• n == edges.length
• 3 ≤ n ≤ 1000
• edges[i].length == 2
• 1 ≤ uᵢ, vᵢ ≤ n
• uᵢ ≠ vᵢ

Pattern Recognition Clues

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

“directed edges”

→ Arrows matter: each node should have one parent, and a node with two parents is a special case.

“rooted tree with one extra edge”

→ Either one node has two parents, or the extra arrow makes a directed cycle.

“the one that occurs last in the input”

→ Among the valid choices, the last arrow in the input wins, so read the input in order.

Approach Complexity Ladder

Brute Force — drop arrows from the last one and test for a rooted treeO(N²)O(N)

Remove arrows from last to first; the first removal that leaves a rooted tree is the answer

Optimal — find the two-parent node, then Union-Find without BO(N · α(N))O(N)

Find a node with two parents (A, B); union every edge except B; a cycle left means drop A, otherwise drop B

Brute Force Intuition

Remove one arrow at a time, starting from the last. Test what remains: no node has two parents, exactly one node has no parent (the root), and a search from the root reaches all n nodes. The first removal that passes 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