🧠 Solving LeetCode Until I Become Top 1% — Day `2`

🔹 Problem: 3372. Maximize the Number of Target Nodes After Connecting Trees I

Difficulty: #Medium
Tags: #Graph #DFS #Tree #GreedyChoice

📝 Problem Summary

2 undirected trees are given, tree1 and tree2, each with n and m nodes respectively and an integer target. Goal is to find the maximum number of nodes in tree2 that can be connected to each node in tree1 such that the length of the path from any node in tree1 to its connected node in tree2 is at most target.
return a list of integers where the i-th element is the maximum number of nodes in tree2 that can be connected to the i-th node in tree1.

🧠 My Thought Process

Brute Force Idea:
I thought it was a greedy algorithm problem because If I take the nodes with the maximum degree in tree2, I can connect them to the nodes in tree1 with the maximum degree. However, this approach doesn't work because it doesn't consider the distance constraint and also I cannot reuse nodes in tree2 for multiple nodes in tree1.
Edge Cases:
What if target is 0?
degree of nodes in tree2 is less than target?
No reuse allowed, what does that even mean?
Solution Idea:
I have no idea how to solve this problem, but the I think it can be a path finding algorithm... Let's ask all developers favorite AI assistant, ChatGPT!
Optimized Strategy:
Chat gpt could do it! But after giving up and looking at the solution, I realized my idea was not that bad. I was actually on the right track. So, here is an explanation of the approach totally not written by ChatGPT:

🧠 Goal

Given two trees (Tree1 and Tree2) and an integer k, for each node in Tree1, find the maximum number of nodes it can reach (including itself) if you connect it to one node in Tree2, such that the total number of edges in any path is ≤ k.

⚙️ Key Idea
- DFS is used to count how many nodes are reachable from each node in a tree within a depth limit (k).
- For each node in Tree1:
- Count how many Tree1 nodes it can reach within k steps → count1[i].
- For Tree2, we precompute how many nodes each of its nodes can reach within k-1 steps → count2.
- We subtract 1 because 1 step is used to connect Tree1 and Tree2.
- Then for each node in Tree1, we greedily assume it connects to the **best possible Tree
Algorithm Used:

e.g. Depth-First Search (DFS) to count reachable nodes within a certain depth.

⚙️ Code Implementation (Python)

class Solution:
    def maxTargetNodes(
        self, edges1: List[List[int]], edges2: List[List[int]], k: int
    ) -> List[int]:

        def dfs(node: int, parent: int, adj: List[List[int]], depth: int) -> int:
            if depth < 0:
                return 0
            count = 1  # include current node
            for neighbor in adj[node]:
                if neighbor == parent:
                    continue
                count += dfs(neighbor, node, adj, depth - 1)
            return count

        def computeReachability(edges: List[List[int]], max_depth: int) -> List[int]:
            n = len(edges) + 1
            adj = [[] for _ in range(n)]
            for u, v in edges:
                adj[u].append(v)
                adj[v].append(u)

            reachable = [0] * n
            for node in range(n):
                reachable[node] = dfs(node, -1, adj, max_depth)
            return reachable

        # Compute reachability in both trees
        count1 = computeReachability(edges1, k)
        count2 = computeReachability(edges2, k - 1)

        # Use the best possible Tree2 node for each Tree1 node
        max_reach_from_tree2 = max(count2)
        return [count1[i] + max_reach_from_tree2 for i in range(len(count1))]

⏱️ Time & Space Complexity

Time: O(N*K + M*K)
Space: O(N + M)

Where N is the number of nodes in tree1 and M is the number of nodes in tree2.

🧩 Key Takeaways

✅ What concept or trick did I learn?
- DFS for Reachability: I don't know how greedy algorithms work, but I learned that using DFS to count reachable nodes within a certain depth is a powerful technique.
💡 What made this problem tricky?
- Understanding Constraints and Hybrid Approach: The problem was tricky because it combined tree traversal with a distance constraint, and I had to think about how to efficiently count reachable nodes without reusing them.
💭 How will I recognize a similar problem in the future?
- Look for Tree Traversal with Constraints: Beware of trees disguised as graphs, especially when distance constraints are involved. If you ever see this animal, don't think, just run(dfs)!