Redundant Connection II - Practice Coding Problems

Redundant Connection II - Problem

In this problem, a rooted tree is a directed graph such that there is exactly one node (the root) for which all other nodes are descendants of this node, plus every node has exactly one parent, except for the root node which has no parents.

The given input is a directed graph that started as a rooted tree with n nodes (with distinct values from 1 to n), with one additional directed edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed.

The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u_i, v_i] that represents a directed edge connecting nodes u_i and v_i, where u_i is a parent of child v_i.

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

Input & Output

Example 1 — Node with Two Parents

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

› Output: [2,3]

💡 Note: Node 3 has two parents: 1 and 2. Removing the later edge [2,3] creates a valid rooted tree with root 1.

Example 2 — Cycle without Double Parent

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

› Output: [4,1]

💡 Note: There's a cycle 1→2→3→4→1. No node has two parents, so we remove the last edge in the cycle.

Example 3 — Simple Case

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

› Output: [3,1]

💡 Note: Forms a cycle 1→2→3→1. The last edge [3,1] creates the cycle, so remove it.

Constraints

3 ≤ edges.length ≤ 1000
edges[i].length == 2
1 ≤ u_i, v_i ≤ edges.length
u_i ≠ v_i

Visualization

Tap to expand

Understanding the Visualization

Input Graph

Rooted tree with one extra edge added

Identify Problem

Find node with 2 parents OR cycle

Remove Edge

Return edge that restores valid tree

Key Takeaway

🎯 Key Insight: Only two cases exist - node with two parents, or cycle without double parents

Asked in

G Google 35 f Facebook 28 a Amazon 22 M Microsoft 18

The key insight is recognizing two cases: a node with two parents, or a cycle without double parents. Best approach uses Union-Find to efficiently detect cycles and handle both cases. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try Each Edge	O(n²)	O(n)	Try removing each edge and check if remaining graph forms valid rooted tree
Union-Find with Case Analysis	O(n)	O(n)	Use Union-Find to detect cycles and handle double-parent scenarios efficiently

Brute Force - Try Each Edge — Algorithm Steps

For each edge from last to first
Remove the edge temporarily
Check if remaining graph is valid rooted tree
If valid, return this edge

Visualization

Tap to expand

Step-by-Step Walkthrough

Try Last Edge

Remove last edge and check if tree is valid

Validate Tree

Count roots - must be exactly 1, no double parents

Found Answer

First valid removal is our answer

Code -

solution.c — C

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

bool isValidTree(int edges[][2], int edgeCount, int skipIndex) {
    int parent[1001];
    bool hasParent[1001];
    bool allNodes[1001];
    
    for (int i = 0; i <= 1000; i++) {
        hasParent[i] = false;
        allNodes[i] = false;
    }
    
    for (int i = 0; i < edgeCount; i++) {
        if (i == skipIndex) continue;
        int u = edges[i][0], v = edges[i][1];
        if (hasParent[v]) {
            return false; // Node has two parents
        }
        parent[v] = u;
        hasParent[v] = true;
        allNodes[u] = true;
        allNodes[v] = true;
    }
    
    // Count roots (nodes with no parent)
    int roots = 0;
    for (int i = 1; i <= 1000; i++) {
        if (allNodes[i] && !hasParent[i]) {
            roots++;
        }
    }
    return roots == 1;
}

int* solution(int** edges, int edgesSize, int* edgesColSize, int* returnSize) {
    *returnSize = 2;
    int* result = (int*)malloc(2 * sizeof(int));
    
    int edgeArray[edgesSize][2];
    for (int i = 0; i < edgesSize; i++) {
        edgeArray[i][0] = edges[i][0];
        edgeArray[i][1] = edges[i][1];
    }
    
    // Try removing each edge from last to first
    for (int i = edgesSize - 1; i >= 0; i--) {
        if (isValidTree(edgeArray, edgesSize, i)) {
            result[0] = edges[i][0];
            result[1] = edges[i][1];
            return result;
        }
    }
    
    result[0] = edges[edgesSize-1][0];
    result[1] = edges[edgesSize-1][1];
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Simple parsing for [[a,b],[c,d],...] format
    int edges[1000][2];
    int edgesSize = 0;
    
    char* ptr = line + 1; // Skip first '['
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            edges[edgesSize][0] = strtol(ptr, &ptr, 10);
            ptr++; // Skip comma
            edges[edgesSize][1] = strtol(ptr, &ptr, 10);
            edgesSize++;
            while (*ptr && *ptr != ']') ptr++;
            if (*ptr == ']') ptr++;
        }
        if (*ptr == ',') ptr++;
    }
    
    int returnSize;
    int** edgesPtrs = (int**)malloc(edgesSize * sizeof(int*));
    for (int i = 0; i < edgesSize; i++) {
        edgesPtrs[i] = edges[i];
    }
    
    int* result = solution(edgesPtrs, edgesSize, NULL, &returnSize);
    printf("[%d,%d]\n", result[0], result[1]);
    
    free(edgesPtrs);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n edges, we validate the entire graph which takes O(n) time

⚠ Quadratic Growth

Space Complexity

O(n)

Hash map to track parent relationships during validation

⚡ Linearithmic Space

98.2K Views

Medium Frequency

~35 min Avg. Time

1.8K 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

Brute Force - Try Each Edge — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler