How hard is LeetCode 685. Redundant Connection II?

LeetCode 685. Redundant Connection II is rated Hard on LeetCode.

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

The Python solution on this page runs in O(n \log n).

What is the space complexity of LeetCode 685. Redundant Connection II?

The Python solution on this page uses O(n), where n is the number of edges auxiliary space.

What topics does LeetCode 685. Redundant Connection II cover?

LeetCode 685. Redundant Connection II is tagged Depth-First Search, Breadth-First Search, Union Find and Graph on LeetCode.

Redundant Connection II — LeetCode 685 Python Solution

HardDepth-First SearchBreadth-First SearchUnion FindGraph

Problem: #685
Pattern: Union-Find
Reading time: 5 min
Source: leetcode.com

The 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.

Example

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

Python solution

Python

class Solution:
    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:
        def find(x: int) -> int:
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        n = len(edges)
        ind = [0] * n
        for _, v in edges:
            ind[v - 1] += 1
        dup = [i for i, (_, v) in enumerate(edges) if ind[v - 1] == 2]
        p = list(range(n))
        if dup:
            for i, (u, v) in enumerate(edges):
                if i == dup[1]:
                    continue
                pu, pv = find(u - 1), find(v - 1)
                if pu == pv:
                    return edges[dup[0]]
                p[pu] = pv
            return edges[dup[1]]
        for i, (u, v) in enumerate(edges):
            pu, pv = find(u - 1), find(v - 1)
            if pu == pv:
                return edges[i]
            p[pu] = pv

Complexity

Measure	Complexity
Time	O(n \log n)
Space	O(n), where n is the number of edges auxiliary

Pattern: Union-Find

Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 685. Redundant Connection II is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.

The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 685. Redundant Connection II?: LeetCode 685. Redundant Connection II is rated Hard on LeetCode.
What is the time complexity of LeetCode 685. Redundant Connection II?: The Python solution on this page runs in O(n \log n).
What is the space complexity of LeetCode 685. Redundant Connection II?: The Python solution on this page uses O(n), where n is the number of edges auxiliary space.
What topics does LeetCode 685. Redundant Connection II cover?: LeetCode 685. Redundant Connection II is tagged Depth-First Search, Breadth-First Search, Union Find and Graph on LeetCode.