How hard is LeetCode 261. Graph Valid Tree?

LeetCode 261. Graph Valid Tree is rated Medium on LeetCode.

What is the time complexity of LeetCode 261. Graph Valid Tree?

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

What is the space complexity of LeetCode 261. Graph Valid Tree?

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

What topics does LeetCode 261. Graph Valid Tree cover?

LeetCode 261. Graph Valid Tree is tagged Depth-First Search, Breadth-First Search, Union Find and Graph on LeetCode.

Is LeetCode 261. Graph Valid Tree a premium problem?

Yes. LeetCode 261. Graph Valid Tree is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Graph Valid Tree — LeetCode 261 Python Solution

MediumLeetCode PremiumDepth-First SearchBreadth-First SearchUnion FindGraph

Problem: #261
Pattern: Union-Find
Reading time: 3 min
Source: leetcode.com

The problem

You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph.

Example

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true

Python solution

Python

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

        p = list(range(n))
        for a, b in edges:
            pa, pb = find(a), find(b)
            if pa == pb:
                return False
            p[pa] = pb
            n -= 1
        return n == 1

Complexity

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

Pattern: Union-Find

Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 261. Graph Valid Tree 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.

On study lists

This problem is on Blind 75 and NeetCode 150.

Frequently asked questions

How hard is LeetCode 261. Graph Valid Tree?: LeetCode 261. Graph Valid Tree is rated Medium on LeetCode.
What is the time complexity of LeetCode 261. Graph Valid Tree?: The Python solution on this page runs in O(n \times \log n).
What is the space complexity of LeetCode 261. Graph Valid Tree?: The Python solution on this page uses O(n), where n is the number of nodes auxiliary space.
What topics does LeetCode 261. Graph Valid Tree cover?: LeetCode 261. Graph Valid Tree is tagged Depth-First Search, Breadth-First Search, Union Find and Graph on LeetCode.
Is LeetCode 261. Graph Valid Tree a premium problem?: Yes. LeetCode 261. Graph Valid Tree is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.