684. Redundant Connection

Problem Statement

In this problem, a tree is an undirected graph that is connected and has no cycles.

You are given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The graph is represented as an array edges of length n where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the graph.

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.

Examples

Example 1:

Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]
Explanation: The edge [2,3] creates a cycle, so it should be removed.

Example 2:

Input: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output: [1,4]
Explanation: The edge [1,4] creates a cycle, so it should be removed.

Constraints

n == edges.length
3 <= n <= 1000
edges[i].length == 2
1 <= ai < bi <= edges.length
ai != bi
There are no repeated edges.
The given graph is connected.

Clarification Questions

Before diving into the solution, here are 5 important clarifications and assumptions to discuss during an interview:

Redundant edge definition: What makes an edge redundant? (Assumption: An edge that creates a cycle in an otherwise tree structure - the edge that forms the cycle)
Graph type: Is the graph directed or undirected? (Assumption: Undirected - edges have no direction)
Tree property: What is the base structure? (Assumption: Graph with n nodes and n edges - one extra edge makes it not a tree)
Return format: What should we return if multiple redundant edges exist? (Assumption: Return the last edge in the input array that creates a cycle)
Edge representation: How are edges represented? (Assumption: [ai, bi] where ai and bi are node labels, 1-indexed per constraints)

Interview Deduction Process (20 minutes)

Step 1: Brute-Force Approach (5 minutes)

Initial Thought: “I need to find redundant edge. Let me check each edge to see if removing it breaks connectivity.”

Naive Solution: For each edge, remove it and check if graph remains connected. If removing edge breaks connectivity, it’s not redundant.

Complexity: O(n²) time, O(n) space

Issues:

O(n²) time - inefficient
Repeats connectivity checks
Doesn’t leverage Union-Find
Can be optimized

Step 2: Semi-Optimized Approach (7 minutes)

Insight: “I can use Union-Find. The first edge that connects already-connected components is redundant.”

Improved Solution: Use Union-Find. Process edges in order. If edge connects already-connected components, it’s redundant. Return first such edge.

Complexity: O(n × α(n)) time, O(n) space

Improvements:

Union-Find efficiently checks connectivity
O(n × α(n)) is nearly linear
Handles all cases correctly
Much more efficient

Step 3: Optimized Solution (8 minutes)

Final Optimization: “Union-Find approach is optimal. Can also use DFS for cycle detection.”

Best Solution: Union-Find is optimal. Process edges, when find(u) == find(v), edge is redundant. Alternative: DFS to find cycle, return last edge in cycle.

Complexity: O(n × α(n)) time, O(n) space

Key Realizations:

Union-Find is perfect for connectivity problems
O(n × α(n)) is nearly linear - very efficient
First edge connecting connected components is redundant
DFS alternative exists but Union-Find is cleaner

Solution Approach

This problem requires finding the edge that creates a cycle in an undirected graph. Since the graph started as a tree (connected, no cycles) and one edge was added, there is exactly one cycle. We need to find and return the redundant edge.

Key Insights:

Cycle Detection: The redundant edge is the one that connects two nodes already in the same connected component
Union-Find (DSU): Efficiently detect cycles by checking if two nodes are already connected before adding an edge
DFS Approach: Build graph and use DFS to detect cycles, then find the last edge in the cycle
Last Edge Priority: If multiple edges form cycles, return the one that appears last in the input

Algorithm Options:

DSU Approach: Process edges in order, return first edge that connects already-connected nodes
DFS Approach: Build graph, find cycle, return last edge in cycle that appears in input

Solution 1: Union-Find (DSU) - Recommended

Solution: DSU with Union by Rank

class DSU{
private:
    vector<int> parent;
    vector<int> rank;

public:
    DSU(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for(int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    int find(int x) {
        if(parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    bool unite(int x, int y) {
        x = find(x);
        y = find(y);
        if(x == y) return false;

        if(rank[x] < rank[y]) {
            parent[x] = y;
        } else if(rank[x] > rank[y]) {
            parent[y] = x;
        } else {
            parent[y] = x;
            rank[x]++;
        }
        return true;
    }
};

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        const int n = edges.size();
        DSU dsu(n);

        for(const auto& edge: edges) {
            if(!dsu.unite(edge[0] - 1, edge[1] - 1)) {
                return edge;
            }
        }
        return {};
    }
};

Algorithm Explanation:

DSU Initialization (Lines 8-15):
- parent[i] = i: Each node is its own parent initially
- rank[i] = 0: All trees start with rank 0
Find with Path Compression (Lines 17-22):
- Recursively find root parent
- Path compression: parent[x] = find(parent[x]) flattens tree
- Returns root of the set containing x
Union by Rank (Lines 24-38):
- Find roots of both nodes
- If same root: already connected → return false (cycle detected!)
- If different roots: merge sets using union by rank
- Attach smaller tree to larger tree to keep balanced
Main Solution (Lines 41-51):
- Process edges in order
- Convert 1-based to 0-based indexing: edge[0] - 1, edge[1] - 1
- If unite returns false: nodes already connected → cycle found!
- Return the redundant edge immediately

Example Walkthrough:

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

Initial: parent = [0,1,2], rank = [0,0,0]

Edge [1,2]: unite(0, 1)
- find(0) = 0, find(1) = 1 (different roots)
- rank[0] == rank[1] → parent[1] = 0, rank[0]++
- parent = [0,0,2], rank = [1,0,0]
- Return true (no cycle)

Edge [1,3]: unite(0, 2)
- find(0) = 0, find(2) = 2 (different roots)
- rank[0] > rank[2] → parent[2] = 0
- parent = [0,0,0], rank = [1,0,0]
- Return true (no cycle)

Edge [2,3]: unite(1, 2)
- find(1) = 0, find(2) = 0 (same root!)
- Return false → CYCLE DETECTED!
- Return [2,3]

Solution 2: DFS Cycle Detection

Solution: DFS to Find Cycle

class Solution {
private:
    int cycleStart = -1;
    void dfs(int src, vector<bool>& visited, vector<vector<pair<int, int>>> adjList, vector<int>& parent) {
        visited[src] = true;
        for(auto& p : adjList[src]) {
            int adj = p.first;
            if(!visited[adj]) {
                parent[adj] = src;
                dfs(adj, visited, adjList, parent);
            } else if(adj != parent[src] && cycleStart == -1) {
                cycleStart = adj;
                parent[adj] = src;
            }
        }
    }

public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        const int n = edges.size();
        vector<bool> visited(n, false);
        vector<int> parent(n, -1);
        vector<vector<pair<int, int>>> adjList(n);
        for(auto& edge: edges) {
            int u = edge[0] - 1;
            int v = edge[1] - 1;
            adjList[u].push_back({v, 0});
            adjList[v].push_back({u, 0});
        }
        dfs(0, visited, adjList, parent);
        unordered_map<int, int> cycleNode;
        int node = cycleStart;
        do {
            cycleNode[node] = 1;
            node = parent[node];
        } while (node != cycleStart);
        for(int i = edges.size() - 1; i >= 0; i--) {
            if(cycleNode[edges[i][0] - 1] &&
            cycleNode[edges[i][1] - 1]) {
                return edges[i];
            }
        }
        return {};
    }
};

Algorithm Explanation:

Graph Construction (Lines 25-32):
- Build adjacency list from edges
- Convert 1-based to 0-based indexing
- Store bidirectional edges
DFS Cycle Detection (Lines 4-16):
- Perform DFS from node 0
- Track parent for each node
- If visiting an already-visited node that’s not the parent: cycle found!
- Mark cycleStart when cycle detected
Cycle Extraction (Lines 33-38):
- Start from cycleStart
- Follow parent pointers to extract all nodes in cycle
- Store cycle nodes in cycleNode map
Find Last Edge in Cycle (Lines 39-44):
- Iterate edges from end to beginning
- Find first edge where both endpoints are in cycle
- Return that edge (last in input order)

Example Walkthrough:

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

Graph:
1 -- 2
|    |
3 ---|

DFS from node 0:
- Visit 0 (node 1), parent[0] = -1
- Visit 1 (node 2), parent[1] = 0
- Visit 2 (node 3), parent[2] = 1
- From 2, try to visit 0 (node 1)
  - 0 is visited and 0 != parent[2] (1) → CYCLE!
  - cycleStart = 0

Extract cycle:
- Start from 0: cycleNode[0] = 1
- parent[0] = -1? No, wait... parent[0] was set to 2 in cycle detection
- Follow: 0 → 2 → 1 → 0
- cycleNode = {0, 1, 2}

Find last edge in cycle:
- Check edges from end: [2,3] → nodes 1,2 both in cycle → Return [2,3]

DSU Template

Here’s the general template for Union-Find (DSU) with union by rank:

class DSU {
private:
    vector<int> parent;
    vector<int> rank;

public:
    DSU(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for(int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    // Find with path compression
    int find(int x) {
        if(parent[x] != x) {
            parent[x] = find(parent[x]); // Path compression
        }
        return parent[x];
    }

    // Union by rank
    bool unite(int x, int y) {
        x = find(x);
        y = find(y);
        if(x == y) return false; // Already in same set

        // Union by rank: attach smaller tree to larger tree
        if(rank[x] < rank[y]) {
            parent[x] = y;
        } else if(rank[x] > rank[y]) {
            parent[y] = x;
        } else {
            parent[y] = x;
            rank[x]++;
        }
        return true;
    }

    // Check if two nodes are connected
    bool connected(int x, int y) {
        return find(x) == find(y);
    }
};

Key Template Components:

Data Structures:
- parent[i]: Parent of node i (root if parent[i] == i)
- rank[i]: Approximate depth of tree rooted at i
Path Compression:
- Flattens tree during find operation
- Makes future finds faster
Union by Rank:
- Keeps trees balanced
- Attaches smaller tree to larger tree
- Only increases rank when ranks are equal
Time Complexity:
- Nearly O(1) per operation (inverse Ackermann function)
- O(α(n)) where α grows extremely slowly

Complexity Analysis

Solution 1: DSU

Time Complexity: O(n × α(n)) ≈ O(n)

DSU operations: O(α(n)) per operation (nearly constant)
Process n edges: O(n × α(n))
Total: O(n) for practical purposes

Space Complexity: O(n)

Parent array: O(n)
Rank array: O(n)
Total: O(n)

Solution 2: DFS

Time Complexity: O(n)

Graph construction: O(n)
DFS traversal: O(n) - visit each node once
Cycle extraction: O(n) - worst case
Edge search: O(n) - check all edges
Total: O(n)

Space Complexity: O(n)

Adjacency list: O(n)
Visited array: O(n)
Parent array: O(n)
Cycle node map: O(n)
DFS recursion stack: O(n)
Total: O(n)

Key Points

DSU is Optimal: Union-Find is the most efficient approach for cycle detection
Path Compression: Speeds up find operations significantly
Union by Rank: Keeps trees balanced for better performance
1-based to 0-based: Convert node indices when using DSU
Last Edge Priority: Problem asks for last edge in input that creates cycle
Single Cycle: Graph has exactly one cycle (one extra edge in tree)

Comparison: DSU vs DFS

Aspect	DSU	DFS
Time Complexity	O(n × α(n)) ≈ O(n)	O(n)
Space Complexity	O(n)	O(n)
Implementation	Simpler	More complex
Cycle Detection	Direct (during union)	Requires traversal
Edge Order	Natural (process in order)	Need to track and search
Recommended	✅ Yes	⚠️ Works but more complex

Alternative Approaches

Approach 1: DSU (Current Solution 1)

Time: O(n × α(n)) ≈ O(n)
Space: O(n)
Best for: Cycle detection in undirected graphs

Approach 2: DFS (Current Solution 2)

Time: O(n)
Space: O(n)
Use case: When you need to extract full cycle information

Approach 3: BFS Cycle Detection

Time: O(n)
Space: O(n)
Similar to DFS: Can detect cycles but more complex

685. Redundant Connection II - Directed graph version
547. Number of Provinces - Count connected components
721. Accounts Merge - DSU for merging accounts
1319. Number of Operations to Make Network Connected - DSU for connectivity

Robina Li

684. Redundant Connection

684. Redundant Connection

Problem Statement

Examples

Constraints

Clarification Questions

Interview Deduction Process (20 minutes)

Step 1: Brute-Force Approach (5 minutes)

Step 2: Semi-Optimized Approach (7 minutes)

Step 3: Optimized Solution (8 minutes)

Solution Approach

Key Insights:

Algorithm Options:

Solution 1: Union-Find (DSU) - Recommended

Solution: DSU with Union by Rank

Algorithm Explanation:

Example Walkthrough:

Solution 2: DFS Cycle Detection

Solution: DFS to Find Cycle

Algorithm Explanation:

Example Walkthrough:

DSU Template

Key Template Components:

Complexity Analysis

Solution 1: DSU

Solution 2: DFS

Key Points

Comparison: DSU vs DFS

Alternative Approaches

Approach 1: DSU (Current Solution 1)

Approach 2: DFS (Current Solution 2)

Approach 3: BFS Cycle Detection

Tags

Related Posts

Recent Posts

684. Redundant Connection

Problem Statement

Examples

Constraints

Clarification Questions

Interview Deduction Process (20 minutes)

Step 1: Brute-Force Approach (5 minutes)

Step 2: Semi-Optimized Approach (7 minutes)

Step 3: Optimized Solution (8 minutes)

Solution Approach

Key Insights:

Algorithm Options:

Solution 1: Union-Find (DSU) - Recommended

Solution: DSU with Union by Rank

Algorithm Explanation:

Example Walkthrough:

Solution 2: DFS Cycle Detection

Solution: DFS to Find Cycle

Algorithm Explanation:

Example Walkthrough:

DSU Template

Key Template Components:

Complexity Analysis

Solution 1: DSU

Solution 2: DFS

Key Points

Comparison: DSU vs DFS

Alternative Approaches

Approach 1: DSU (Current Solution 1)

Approach 2: DFS (Current Solution 2)

Approach 3: BFS Cycle Detection

Related Problems

Tags

Related Posts

Recent Posts