Crack the Backend

Problem Statement

The graph has n nodes (1..n) and n edges — so it is a tree plus one extra edge, and has exactly one cycle. Return an edge that can be removed so the graph becomes a tree. If multiple such edges exist, return the one that appears last in edges.

Key Observations

Union Find: Process edges in order. For each edge (u, v): if u and v are already in the same set (already connected), then this edge is redundant (it creates the cycle). Return this edge. Otherwise union u and v and continue. We are guaranteed exactly one cycle, so we will find exactly one such edge.

Approach

High-level: UF. For each (u,v): if find(u) == find(v) return [u,v]; else union(u,v). Return [] (shouldn't happen).

Steps: int[] parent = new int[n+1]; for (i=1;i<=n;i++) parent[i]=i; for (int[] e : edges) { if (find(e[0])==find(e[1])) return e; union(e[0],e[1]); } return new int[0];

Implementation

Java

int[] parent;
int find(int x) { return parent[x] == x ? x : (parent[x] = find(parent[x])); }

public int[] findRedundantConnection(int[][] edges) {
    int n = edges.length;
    parent = new int[n + 1];

    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }

    for (int[] e : edges) {
        if (find(e[0]) == find(e[1])) {
            return e;
        }

        parent[find(e[0])] = find(e[1]);
    }

    return new int[0];
}

Test Cases

Example 1

Input

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

Expected

[2,3]

Explanation

Remove [2,3] to get tree.

Complexity Analysis

Time: O(n α(n)) ≈ O(n).
Space: O(n).

Follow-ups

Path compression + rank for optimal UF.