Tree of Coprimes — LeetCode 1766 Python Solution
HardTreeDepth-First SearchArrayMathNumber Theory
- Problem
- #1766
- Pattern
- Tree Traversal
- Reading time
- 5 min
- Source
- leetcode.com
The problem
There is a tree (i.e., a connected, undirected graph that has no cycles) consisting of n nodes numbered from 0 to n - 1 and exactly n - 1 edges. Each node has a value associated with it, and the root of the tree is node 0.
Example
- Input
- nums = [2,3,3,2], edges = [[0,1],[1,2],[1,3]]
- Output
- [-1,0,0,1]
- Explanation
- In the above figure, each node's value is in parentheses.
Python solution
Python
class Solution:
def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:
def dfs(i, fa, depth):
t = k = -1
for v in f[nums[i]]:
stk = stks[v]
if stk and stk[-1][1] > k:
t, k = stk[-1]
ans[i] = t
for j in g[i]:
if j != fa:
stks[nums[i]].append((i, depth))
dfs(j, i, depth + 1)
stks[nums[i]].pop()
g = defaultdict(list)
for u, v in edges:
g[u].append(v)
g[v].append(u)
f = defaultdict(list)
for i in range(1, 51):
for j in range(1, 51):
if gcd(i, j) == 1:
f[i].append(j)
stks = defaultdict(list)
ans = [-1] * len(nums)
dfs(0, -1, 0)
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n \times M) |
| Space | O(M^2 + n) auxiliary |
Pattern: Tree Traversal
Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 1766. Tree of Coprimes is filed here because LeetCode tags it Tree, which is the vocabulary this hub collects.
The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.
Related problems
LeetCode 2440Create Components With Same ValueHardLeetCode 2049Count Nodes With the Highest ScoreMediumLeetCode 2322Minimum Score After Removals on a TreeHardLeetCode 2458Height of Binary Tree After Subtree Removal QueriesHardLeetCode 98Validate Binary Search TreeMediumLeetCode 99Recover Binary Search TreeMedium
Frequently asked questions
- How hard is LeetCode 1766. Tree of Coprimes?
- LeetCode 1766. Tree of Coprimes is rated Hard on LeetCode.
- What is the time complexity of LeetCode 1766. Tree of Coprimes?
- The Python solution on this page runs in O(n \times M).
- What is the space complexity of LeetCode 1766. Tree of Coprimes?
- The Python solution on this page uses O(M^2 + n) auxiliary space.
- What topics does LeetCode 1766. Tree of Coprimes cover?
- LeetCode 1766. Tree of Coprimes is tagged Tree, Depth-First Search, Array, Math and Number Theory on LeetCode.