D
DevExCode

LeetCode 685: Redundant Connection II Solution

Master LeetCode problem 685 (Redundant Connection II), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation

To solve this problem, we can use a variation of Union-Find algorithm. The given problem can have three different cases:

  1. A node has two parents (Case 1).
  2. The tree has a cycle (Case 2).
  3. A node is its own parent (Case 3).

We need to handle these cases strategically to find the redundant edge.

Algorithm:

  1. Initialize a parent array to keep track of the parent node for each node.
  2. Iterate through the edges:
    • For each edge [u, v], if v already has a parent assigned (Case 1), mark both u and v as parents and store these two edges.
    • If v does not have a parent assigned yet, assign u as the parent of v.
  3. Detect the cycle (Case 2) using Union-Find algorithm. If a cycle is found, return the second edge that creates the cycle.
  4. If there is no cycle, return the first edge found in Case 1.

Time Complexity: O(n) Space Complexity: O(n)

Solution Code

class Solution {
    public int[] findRedundantDirectedConnection(int[][] edges) {
        int n = edges.length;
        int[] parent = new int[n + 1];
        int[] candidate1 = null, candidate2 = null;
        
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1];
            if (parent[v] != 0) {
                candidate1 = new int[]{parent[v], v};
                candidate2 = new int[]{u, v};
            } else {
                parent[v] = u;
            }
        }
        
        int[] roots = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            roots[i] = i;
        }
        
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1];
            if (candidate2 == null && roots[v] == v) {
                roots[v] = u;
            } else if (find(roots, u) == v) {
                return candidate1 == null ? edge : candidate1;
            }
        }
        
        return candidate2;
    }
    
    public int find(int[] roots, int node) {
        while (roots[node] != node) {
            roots[node] = roots[roots[node]];
            node = roots[node];
        }
        return node;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 685 (Redundant Connection II)?

This page provides optimized solutions for LeetCode problem 685 (Redundant Connection II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 685 (Redundant Connection II)?

The time complexity for LeetCode 685 (Redundant Connection II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 685 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 685 in Java, C++, or Python.

Back to LeetCode Solutions