Difficulty: MediumGraphs

Redundant Connection

Problem in Plain English

A tree of nodes labelled 1 to n has one extra edge added, which creates exactly one cycle. Return the last input edge whose removal turns the graph back into a tree.

Problem Statement

You are given an undirected graph that started as a tree with n nodes labelled from 1 to n, with one additional edge added. The added edge connects two different vertices, and it was not an edge that already existed.

Return an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input.

Constraints

n == edges.length
3 <= n <= 1000
edges[i].length == 2
1 <= ai < bi <= n
No edge appears twice in the input.
The given graph is connected.

Examples

Example 1

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

Edges (1,2) and (1,3) already connect all three nodes, so adding (2,3) closes the only cycle and removing it restores a tree.

Example 2

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

The first three edges plus (1,4) form the cycle 1-2-3-4-1, and (1,4) is the last edge of that cycle in the input.

Example 3

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

The triangle 1-2-3-1 is the only cycle, and [1,3] is its last input edge. Later edges [3,4] and [4,5] are bridges: removing either disconnects the graph. The answer is therefore not the last edge overall.

Example 4

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

All three triangle edges can be removed to restore a tree. Their order makes [1,2] the answer, even though it is lexicographically smallest.

Intuition

A tree has a unique path between any two nodes. Adding one edge creates exactly one cycle; removing any edge on that cycle restores a tree, but the input order decides which one to return. In Example 1, when [2,3] arrives, earlier edges already provide 2 -> 1 -> 3. This is the last edge of the only cycle, even if later input edges exist outside the cycle. We can detect the existing path by a graph search or remember connected groups with union find.

Approaches

Path Check Per Edge

Solution Details

Reveal Path Check Per Edge: intuition, complexity, and code

Intuition

Check whether an edge closes an existing path before adding it to an undirected adjacency list. Searching through earlier edges makes the cycle condition concrete, but repeats up to a full graph traversal for each insertion. An explicit DFS stack handles a 1000-node chain without depending on recursion depth.

Step-by-Step Logic

Allocate an adjacency list for labels 1 through n, including unused index 0. Scan edges in their original order. In Example 1, n = 3 and every list begins empty.
For each [u,v], initialize a fresh seen array and stack containing u. Pop vertices until v is reached or the stack empties; mark neighbours before pushing. With [1,2], only vertex 1 is visited, so no path exists.
If no path exists, insert the edge in both endpoint lists. After [1,2] and then [1,3], the earlier graph is 2-1-3. The second search visits 1 then 2 without reaching 3.
If the search reaches v, return a fresh [u,v] pair without inserting it. At [2,3], the stack visits 2, 1, then 3, certifying the existing path 2 -> 1 -> 3.
Immediate return produces [2,3] in Example 1. The single-cycle promise proves it is the last cycle edge, even if bridges appear later; the defensive empty return is unreachable for valid inputs.

Why It Works

An iterative DFS discovers precisely the vertices reachable from the first endpoint using accepted earlier edges; each push extends an existing path and every adjacency is eventually checked if the target is absent. Marking at push time prevents repeated processing. Before each insertion, the accepted earlier edges form a forest. If no path joins the endpoints, inserting the edge connects different components and cannot create a cycle. If a path exists, that path plus the new edge is a cycle. The complete input has exactly one cycle, so the first failed insertion is exactly the last input edge on that cycle: all its other cycle edges are already present, while earlier cycle edges could not have completed it. Removing this edge leaves the original connected graph acyclic, hence a tree. Later edges outside the cycle are bridges and cannot change the answer, so immediate return satisfies the last-edge rule.

Dry Run

Path Check Per Edge: variable states at each step
Edge	Popped node	Stack after	Seen labels	Reach target?	Adjacency / action
[1,2]	1	[]	{1}	no; exhausted	insert; 1:[2], 2:[1], 3:[]
[1,3]	1	[2]	{1,2}	no	unchanged
[1,3]	2	[]	{1,2}	no; exhausted	insert; 1:[2,3], 2:[1], 3:[1]
[2,3]	2	[1]	{1,2}	no	unchanged
[2,3]	1	[3]	{1,2,3}	no	unchanged
[2,3]	3	[]	{1,2,3}	yes	return fresh [2,3]; do not insert

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(n)

Here n is both the number of vertices and input edges. Before failure the stored graph is a forest with at most n-1 edges. Each search initializes n+1 markers and examines O(n) vertices and adjacency entries; at most n searches give O(n^2) time. The adjacency lists store O(n) entries, and one seen array and stack use O(n) live space. Fresh search arrays create O(n^2) cumulative allocation across the run but only O(n) working space at a time. The returned two-element copy uses O(1) space; input edges and their row identities remain unchanged.

Code

Solution.java

1import java.util.*;2
3class Solution {4    public int[] findRedundantConnection(int[][] edges) {5        int n = edges.length;6        List<List<Integer>> graph = new ArrayList<>();7        for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());8        for (int[] edge : edges) {9            int u = edge[0], v = edge[1];10            boolean[] seen = new boolean[n + 1];11            Deque<Integer> stack = new ArrayDeque<>();12            stack.push(u);13            seen[u] = true;14            while (!stack.isEmpty()) {15                int node = stack.pop();16                // Check before insertion: the edge must not provide its own path.17                if (node == v) return new int[]{u, v};18                for (int next : graph.get(node)) {19                    if (!seen[next]) {20                        seen[next] = true; // Prevent duplicate pushes in undirected traversal.21                        stack.push(next);22                    }23                }24            }25            graph.get(u).add(v);26            graph.get(v).add(u);27        }28        return new int[0];29    }30}

Hints

Hint 1

A connected graph with n vertices and n edges has exactly one cycle. Every removable edge lies on that cycle.

Hint 2

Before inserting [u,v], ask whether earlier edges already connect u and v. The insertion that first finds a path is the last input edge on the unique cycle.

Hint 3

A disjoint set represents components with roots; equal roots detect a cycle, different roots can be merged. Use path halving and union by size.

Edge Cases

The three-node triangle is the minimum input; changing its edge order changes the answer.
A cycle can complete before the last input edge. Later bridges do not replace the answer, as in Example 3.
A 1000-node chain plus a closing edge requires a deep path check; an explicit stack handles it under ordinary recursion limits.
Node n is a legal endpoint, so allocate n+1 positions for 1-based labels. The answer is an original ordered endpoint pair, not a pair of representatives.

Common Mistakes and Interview Tips

Claiming the first cycle-closing edge is wrong because the statement says last: under the single-cycle promise they are the same edge. Explain why all earlier cycle edges must precede that closure.
Returning the final input edge or sorting edges violates the input-order tie-break. A later bridge cannot be removed without disconnection.
Inserting an edge before the DFS check lets the new edge supply its own endpoint path. Store each accepted edge in both directions.
Merging endpoint labels rather than their component roots can split the parent invariant. Update and compare component sizes only at roots.
Calling the size array rank obscures the implementation: sizes add after union, while rank tracks a height bound and increments only on a tie.
Returning an input edge row aliases caller-owned storage in Java. These snippets return a fresh pair in every language and leave every input row untouched.
Interview tip: distinguish amortized O(alpha(n)) per union-find operation from strict constant time; show how the single-cycle assumption justifies early return.

Key Takeaway

When undirected edges arrive in order, track connected components to answer whether the next edge closes an existing path. A single-cycle promise turns the first failed union into the last cycle edge required by the input-order tie-break.