Introduction

In this blog post, we will explore how to solve the LeetCode problem "2368" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

There is an undirected tree with n nodes labeled from 0 to n - 1 and n - 1 edges. You are given a 2D integer array edges of length n - 1 where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree. You are also given an integer array restricted which represents restricted nodes. Return the maximum number of nodes you can reach from node 0 without visiting a restricted node. Note that node 0 will not be a restricted node. Example 1: Input: n = 7, edges = [[0,1],[1,2],[3,1],[4,0],[0,5],[5,6]], restricted = [4,5] Output: 4 Explanation: The diagram above shows the tree. We have that [0,1,2,3] are the only nodes that can be reached from node 0 without visiting a restricted node. Example 2: Input: n = 7, edges = [[0,1],[0,2],[0,5],[0,4],[3,2],[6,5]], restricted = [4,2,1] Output: 3 Explanation: The diagram above shows the tree. We have that [0,5,6] are the only nodes that can be reached from node 0 without visiting a restricted node. Constraints: 2 <= n <= 105 edges.length == n - 1 edges[i].length == 2 0 <= ai, bi < n ai != bi edges represents a valid tree. 1 <= restricted.length < n 1 <= restricted[i] < n All the values of restricted are unique.

Explanation

Here's the approach to solve this problem:

• Build Adjacency List: Construct an adjacency list representation of the tree using the given edges.
• Breadth-First Search (BFS): Perform a BFS starting from node 0. During the traversal, only visit nodes that are not in the restricted set.

• Count Reachable Nodes: Keep track of the number of reachable nodes during the BFS.

• Runtime Complexity: O(N), where N is the number of nodes. Storage Complexity: O(N)

Code

    from collections import deque

def reachableNodes(n: int, edges: list[list[int]], restricted: list[int]) -> int:
    """
    Calculates the maximum number of nodes reachable from node 0 without visiting a restricted node.

    Args:
        n: The number of nodes in the tree.
        edges: A list of edges representing the tree.
        restricted: A list of restricted nodes.

    Returns:
        The maximum number of reachable nodes from node 0.
    """

    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    restricted_set = set(restricted)
    q = deque([0])
    visited = {0}
    count = 0

    while q:
        node = q.popleft()
        count += 1

        for neighbor in adj[node]:
            if neighbor not in restricted_set and neighbor not in visited:
                q.append(neighbor)
                visited.add(neighbor)

    return count