This is a classic problem for testing understanding of graph connectivity and cycle detection, making it a popular interview question at companies like Amazon.

Brute Force Approach for Redundant Connection

A naive approach to solving the Redundant Connection problem involves checking the connectivity of the graph incrementally using standard traversal algorithms like Depth-First Search (DFS) or Breadth-First Search (BFS).

The logic proceeds as follows:

1. Initialize an empty graph.
2. Iterate through the input edges one by one.
3. For each edge [u, v], before adding it to the graph, perform a DFS or BFS to check if a path already exists between node u and node v.
4. If a path already exists, adding edge [u, v] would create a cycle. Since we are processing edges in the order given, this edge is the one that completes the cycle and is "redundant" according to the problem constraints (specifically the "last occurring" requirement).
5. If no path exists, add the edge to the graph and continue.

Pseudo-code

text
function findRedundantConnection(edges):
    graph = empty adjacency list
    
    for each edge [u, v] in edges:
        if hasPath(u, v, graph):  // Perform DFS/BFS
            return [u, v]
        add edge [u, v] to graph
        
    return []

Complexity Analysis

The time complexity of this brute force approach is O(N²). In the worst case, for every edge we process, we might traverse the entire graph built so far to check for connectivity. Since there are $N$ edges and each DFS/BFS takes $O(N)$ time, the total work is quadratic.

While $O(N^2)$ might pass for small constraints ($N \le 1000$), it is inefficient compared to the optimal solution. The primary failure of this approach is that it repeats the work of traversing the graph for every new edge, failing to leverage the state of connected components efficiently.

Core Insight for Redundant Connection

The key intuition for the optimal solution lies in the definition of a tree and a cycle. A tree is a connected graph with no cycles. If we start with $N$ isolated nodes and add edges one by one, we are essentially merging separate trees (or components) together.

As long as an edge connects two nodes that are currently in different components, that edge is necessary for connectivity; it acts as a bridge merging two separate sets. However, if we encounter an edge [u, v] where u and v are already in the same component (i.e., they share a common root or ancestor), adding this edge creates a path back to a node already reachable, thus forming a cycle.

Because the problem asks for the edge occurring last in the input that can be removed, and we process the input array linearly, the very first time we encounter an edge connecting two already-connected nodes, that edge is the one that "closes" the loop. In the context of the input order, this is the redundant connection.

Visual Description: Imagine the $N$ nodes as $N$ distinct sets.

1. Initially, every node is its own parent.
2. When we process an edge [1, 2], we verify the roots of 1 and 2. If they are different, we merge them. Now {1, 2} is one set.
3. If we later process [2, 3], we merge node 3 into the set {1, 2}. Now {1, 2, 3} is one set.
4. Finally, if we see an edge [1, 3], we check the roots. Both 1 and 3 belong to the same set. This implies a path already exists between them (via 2). Therefore, [1, 3] is the redundant edge.

Algorithm Strategy: Graph - Union-Find (Disjoint Set Union - DSU)

We will implement the Union-Find data structure to solve this efficiently. The strategy relies on maintaining a parent array where parent[i] points to the parent of node i.

1. Initialization: Create a parent array of size $N+1$ (since nodes are 1-indexed). Initially, every node is its own parent (parent[i] = i).
2. Find Operation: To find the representative (root) of a node, we follow the parent pointers until we reach a node that is its own parent. We apply path compression here: as we traverse up the tree, we update the parent of each visited node to point directly to the root. This flattens the structure, ensuring future queries are nearly $O(1)$.
3. Union Operation: To connect two nodes u and v, we find their roots. If the roots are different, we set the parent of one root to be the other. We can use union by rank (attaching the shorter tree to the taller tree) to further optimize, though path compression alone is usually sufficient for interview code.
4. Cycle Detection: Iterate through the input edges. For each edge [u, v]:
   • Find rootU = find(u) and rootV = find(v).
   • If rootU == rootV, it means u and v are already connected. This edge closes a cycle. Return [u, v].
   • Otherwise, perform union(rootU, rootV) to merge the sets.

Execution Flow

Let's trace the algorithm with Example 1: edges = [[1,2], [1,3], [2,3]].

1. Setup:

   • parent array: [0, 1, 2, 3] (indices 1, 2, 3 are relevant).

2. Process Edge [1, 2]:

   • find(1) returns 1.
   • find(2) returns 2.
   • Roots are different. Union them. Let's set parent[2] = 1.
   • parent: [0, 1, 1, 3]. Set {1, 2} is connected.

3. Process Edge [1, 3]:

   • find(1) returns 1.
   • find(3) returns 3.
   • Roots are different. Union them. Set parent[3] = 1.
   • parent: [0, 1, 1, 1]. Set {1, 2, 3} is connected.

4. Process Edge [2, 3]:

   • find(2): 2 -> 1. Returns 1.
   • find(3): 3 -> 1. Returns 1.
   • Roots are identical (1 == 1).
   • This implies 2 and 3 are already connected.
   • Result: Return [2, 3].

Proof of Correctness

The algorithm relies on the invariant that the parent array correctly partitions nodes into disjoint sets based on the edges processed so far.

1. Connectivity: If find(u) == find(v), there exists a path between u and v using previously processed edges.
2. Cycle Property: Adding an edge between two nodes already in the same connected component creates a cycle.
3. Last Occurrence: Since we process edges in the order given in the input, the first edge we encounter that creates a cycle is necessarily the one that completes the cycle relative to the edges before it. If we view the graph construction temporally, this edge is the "last" one needed to form the loop involving the nodes it connects.

Thus, the first edge that fails the union check is the correct answer.

Reference Implementation

C++ Solution for LeetCode 684

cpp
class Solution {
    vector<int> parent;

    // Find function with path compression
    int find(int i) {
        if (parent[i] == i) {
            return i;
        }
        // Path compression: point node directly to root
        return parent[i] = find(parent[i]);
    }

    // Union function
    void unite(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);
        if (rootI != rootJ) {
            parent[rootI] = rootJ;
        }
    }

public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        // Initialize parent array. Nodes are 1-indexed.
        parent.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }

        for (const auto& edge : edges) {
            int u = edge[0];
            int v = edge[1];
            
            // If roots are the same, this edge creates a cycle
            if (find(u) == find(v)) {
                return edge;
            }
            
            // Otherwise, merge the sets
            unite(u, v);
        }

        return {}; // Should not reach here given problem constraints
    }
};

Java Solution for LeetCode 684

java
class Solution {
    private int[] parent;

    private int find(int i) {
        if (parent[i] == i) {
            return i;
        }
        // Path compression
        parent[i] = find(parent[i]);
        return parent[i];
    }

    private void union(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);
        if (rootI != rootJ) {
            parent[rootI] = rootJ;
        }
    }

    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        parent = new int[n + 1];
        
        // Initialize parent pointers
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }

        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            
            // If they share the same root, we found the cycle
            if (find(u) == find(v)) {
                return edge;
            }
            
            union(u, v);
        }

        return new int[0];
    }
}

Python Solution for LeetCode 684

python
class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        parent = list(range(len(edges) + 1))

        def find(i):
            if parent[i] != i:
                # Path compression
                parent[i] = find(parent[i])
            return parent[i]

        def union(i, j):
            root_i = find(i)
            root_j = find(j)
            if root_i != root_j:
                parent[root_i] = root_j
                return True
            return False

        for u, v in edges:
            # If union returns False, roots were already same -> cycle detected
            if not union(u, v):
                return [u, v]
                
        return []