Redundant Connection - Practice Coding Problems

Redundant Connection - Problem

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] = [a_i, b_i] indicates that there is an edge between nodes a_i and b_i 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.

Input & Output

Example 1 — Basic Triangle

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

› Output: [2,3]

💡 Note: We have nodes 1,2,3. Edges [1,2] and [1,3] form a valid tree. Adding [2,3] creates a cycle 1-2-3-1, so [2,3] is redundant.

Example 2 — Square with Diagonal

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

› Output: [1,4]

💡 Note: Path 1-2-3-4 already connects nodes 1 and 4. Edge [1,4] creates cycle and occurs last among cycle-creating edges.

Example 3 — Linear with Back Edge

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

› Output: [1,3]

💡 Note: Edges [1,2] and [2,3] form path 1-2-3. Adding [1,3] creates cycle 1-2-3-1, and [1,3] is the last edge.

Constraints

3 ≤ edges.length ≤ 1000
edges[i].length == 2
1 ≤ a_i < b_i ≤ edges.length

Visualization

Tap to expand

Understanding the Visualization

Input: Tree + 1 Edge

Graph with n nodes and n edges (one extra)

Process: Find Cycle

Identify which edge creates the cycle

Output: Redundant Edge

Return the last edge that completes a cycle

Key Takeaway

🎯 Key Insight: The redundant edge always connects two nodes that are already connected through other paths

Asked in

a Amazon 15 G Google 12 f Facebook 8 M Microsoft 6

The key insight is to detect when adding an edge would create a cycle. The Union-Find approach is optimal, tracking connected components efficiently. When two nodes are already in the same component, their connecting edge is redundant. Time: O(n⋅α(n)), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ DFS Cycle Detection	O(n²)	O(n)	Use DFS to detect cycles and identify the redundant edge during traversal
Brute Force - Try Removing Each Edge	O(n³)	O(n)	Try removing each edge and check if the remaining graph is a valid tree
Union-Find (Disjoint Set)	O(n⋅α(n))	O(n)	Use Union-Find to efficiently detect when two nodes are already in same connected component

DFS Cycle Detection — Algorithm Steps

Step 1: Process edges one by one
Step 2: Before adding each edge, check if nodes are already connected
Step 3: Use DFS to detect existing path
Step 4: Return the edge that creates a cycle

Visualization

Tap to expand

Step-by-Step Walkthrough

Process Edges

Add edges one by one to build graph

Check Connectivity

Before adding edge, use DFS to check if nodes already connected

Found Cycle

When nodes already connected, current edge creates cycle

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int** edges, int edgesSize, int* returnSize) {
    *returnSize = 2;
    int adj[edgesSize + 1][edgesSize + 1];
    memset(adj, 0, sizeof(adj));
    
    // Helper function for DFS path checking
    int hasPath(int start, int end, int visited[]) {
        if (start == end) return 1;
        visited[start] = 1;
        
        for (int i = 1; i <= edgesSize; i++) {
            if (adj[start][i] && !visited[i]) {
                if (hasPath(i, end, visited)) {
                    return 1;
                }
            }
        }
        return 0;
    }
    
    for (int i = 0; i < edgesSize; i++) {
        int u = edges[i][0];
        int v = edges[i][1];
        
        // Check if there's already a path between u and v
        int visited[edgesSize + 1];
        memset(visited, 0, sizeof(visited));
        
        if (hasPath(u, v, visited)) {
            int* result = (int*)malloc(2 * sizeof(int));
            result[0] = u;
            result[1] = v;
            return result;
        }
        
        // Add the edge
        adj[u][v] = adj[v][u] = 1;
    }
    
    int* result = (int*)malloc(2 * sizeof(int));
    result[0] = edges[edgesSize-1][0];
    result[1] = edges[edgesSize-1][1];
    return result;
}

int main() {
    int** edges = (int**)malloc(3 * sizeof(int*));
    for (int i = 0; i < 3; i++) {
        edges[i] = (int*)malloc(2 * sizeof(int));
    }
    
    edges[0][0] = 1; edges[0][1] = 2;
    edges[1][0] = 1; edges[1][1] = 3;
    edges[2][0] = 2; edges[2][1] = 3;
    
    int returnSize;
    int* result = solution(edges, 3, &returnSize);
    printf("[%d,%d]\n", result[0], result[1]);
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each edge, we run DFS which can take O(n) time

⚠ Quadratic Growth

Space Complexity

O(n)

Space for adjacency list and recursion stack in DFS

⚡ Linearithmic Space

180.0K Views

Medium Frequency

~15 min Avg. Time

4.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

DFS Cycle Detection — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler