Problem of The Day: Set Matrix Zeroes

5 min read 1024 words

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