Problem of The Day: Set Matrix Zeroes

Problem Statement

leetcode problem link

Intuition

The problem requires finding the maximum number of reachable nodes by combining two graphs. We use BFS to explore nodes within a given distance limit in both graphs and combine their results.

Approach [Accepted]

1. Create adjacency lists for both graphs using the given edges
2. Use BFS to count reachable nodes:
   • For graph1: use distance limit k
   • For graph2: use distance limit k-1
3. Find maximum reachable nodes from graph2
4. Combine results by adding each node’s count from graph1 with the maximum from graph2

Complexity

• Time complexity: O(V₁E₁ + V₂E₂)

  • V₁, E₁: vertices and edges in graph1
  • V₂, E₂: vertices and edges in graph2

• Space complexity: O(V₁ + E₁ + V₂ + E₂)

  • Space for adjacency lists and BFS queue/visited set

Code

class Solution:
    def maxTargetNodes(self, edges1: List[List[int]], edges2: List[List[int]], k: int) -> List[int]:
        n = len(edges1) + 1
        m = len(edges2) + 1
        graph1 = {i: [] for i in range(n)}
        graph2 = {j: [] for j in range(m)}
        nodes1 = {i: 0 for i in range(n)}
        nodes2 = {j: 0 for j in range(m)}
        res = []

        # print(graph1, n)
        # print(graph2, m)

        for u, v in edges1:
            graph1[u].append(v)
            graph1[v].append(u)
        for u, v in edges2:
            graph2[u].append(v)
            graph2[v].append(u)

        def bfs(start, graph, nodes, limit=k):
            queue = deque([[start, 0]])
            visited = set()
            visited.add(start)
            count = 0
            while queue:
                node, level = queue.popleft()
                count += 1
                for nei in graph[node]:
                    if nei not in visited and level + 1 <= limit:
                        queue.append([nei, level + 1])
                        visited.add(nei)
            nodes[start] = count

        max_nodes2 = 0
        for i in range(n):
            bfs(i, graph1, nodes1)

        if k - 1 >= 0:
            for i in range(m):
                bfs(i, graph2, nodes2, k - 1)
                max_nodes2 = max(max_nodes2, nodes2[i])

        # print(nodes1)
        # print(nodes2)
        # print(max_nodes2)

        for i in range(n):
            res.append(nodes1[i] + max_nodes2)

        return res

Editorial

Approach: Depth-First Search

class Solution:
    def maxTargetNodes(
        self, edges1: List[List[int]], edges2: List[List[int]], k: int
    ) -> List[int]:
        def dfs(
            node: int, parent: int, children: List[List[int]], k: int
        ) -> int:
            if k < 0:
                return 0
            res = 1
            for child in children[node]:
                if child == parent:
                    continue
                res += dfs(child, node, children, k - 1)
            return res

        def build(edges: List[List[int]], k: int) -> List[int]:
            n = len(edges) + 1
            children = [[] for _ in range(n)]
            for u, v in edges:
                children[u].append(v)
                children[v].append(u)
            res = [0] * n
            for i in range(n):
                res[i] = dfs(i, -1, children, k)
            return res

        n = len(edges1) + 1
        count1 = build(edges1, k)
        count2 = build(edges2, k - 1)
        maxCount2 = max(count2)
        res = [count1[i] + maxCount2 for i in range(n)]
        return res