Problem of The Day: Build a Matrix With Conditions

Problem Statement

Intuition

To solve this problem, the key insight is to perform topological sorting on the given row and column conditions. Topological sorting helps us determine the order in which elements should appear based on their dependencies.

Approach

1. Topological Sort:

   • Perform topological sorting on the rowConditions to determine the order of rows.
   • Perform topological sorting on the colConditions to determine the order of columns.
   • If a cycle is detected during the sorting process, return an empty matrix since it’s impossible to satisfy the given conditions.

2. Matrix Construction:

   • Use the results of the topological sorts to map each element to its respective row and column.
   • Create an empty matrix of size k x k.
   • Place each element in the matrix according to the determined row and column positions.

Complexity

• Time Complexity:

  • Topological sort involves visiting each node and edge, giving a complexity of (O(V + E)), where (V) is the number of vertices (in this case, (k)) and (E) is the number of edges (given by rowConditions and colConditions).
  • Thus, the overall time complexity is (O(k + \text{len(rowConditions)} + \text{len(colConditions)})).

• Space Complexity:

  • Storing the adjacency list requires (O(k + \text{len(rowConditions)} + \text{len(colConditions)})).
  • Additionally, storing the matrix requires (O(k^2)).
  • Therefore, the overall space complexity is (O(k^2 + \text{len(rowConditions)} + \text{len(colConditions)})).

Code

Code from NeetCodeIO

class Solution:
    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:
        def dfs(src, adj, visited, path, order):
            if src in path:
                return False
            if src in visited:
                return True

            visited.add(src)
            path.add(src)
            for nei in adj[src]:
                if not dfs(nei, adj, visited, path, order):
                    return False
            path.remove(src)
            order.append(src)
            return True

        def topological_sort(edges):
            adj = defaultdict(list)
            for src, dst in edges:
                adj[src].append(dst)

            visited, path = set(), set()
            order = []
            for src in range(1, k + 1):
                if not dfs(src, adj, visited, path, order):
                    return []
            return order[::-1]

        def build_matrix():
            row_order = topological_sort(rowConditions)
            col_order = topological_sort(colConditions)

            if not row_order or not col_order:
                return []

            val_to_row = {n: i for i, n in enumerate(row_order)}
            val_to_col = {n: i for i, n in enumerate(col_order)}

            mat = [[0] * k for _ in range(k)]

            for num in range(1, k + 1):
                r, c = val_to_row[num], val_to_col[num]
                mat[r][c] = num
            return mat

        return build_matrix()

Editorial

Approach 1: Depth-First Search

class Solution:
    def buildMatrix(
        self,
        k: int,
        rowConditions: List[List[int]],
        colConditions: List[List[int]],
    ) -> List[List[int]]:
        # Store the topologically sorted sequences.
        order_rows = self.__topoSort(rowConditions, k)
        order_columns = self.__topoSort(colConditions, k)

        # If no topological sort exists, return empty array.
        if not order_rows or not order_columns:
            return []
        matrix = [[0] * k for _ in range(k)]
        pos_row = {num: i for i, num in enumerate(order_rows)}
        pos_col = {num: i for i, num in enumerate(order_columns)}

        for num in range(1, k + 1):
            if num in pos_row and num in pos_col:
                matrix[pos_row[num]][pos_col[num]] = num
        return matrix

    def __topoSort(self, edges: List[List[int]], n: int) -> List[int]:
        adj = defaultdict(list)
        order = []
        visited = [0] * (n + 1)
        has_cycle = [False]

        # Build adjacency list
        for x, y in edges:
            adj[x].append(y)
        # Perform DFS for each node
        for i in range(1, n + 1):
            if visited[i] == 0:
                self.__dfs(i, adj, visited, order, has_cycle)
                # Return empty if cycle detected
                if has_cycle[0]:
                    return []
        # Reverse to get the correct order
        order.reverse()
        return order

    def __dfs(
        self,
        node: int,
        adj: defaultdict,
        visited: List[int],
        order: List[int],
        has_cycle: List[bool],
    ):
        # Mark node as visiting
        visited[node] = 1
        for neighbor in adj[node]:
            if visited[neighbor] == 0:
                self.__dfs(neighbor, adj, visited, order, has_cycle)
                # Early exit if a cycle is detected
                if has_cycle[0]:
                    return
            elif visited[neighbor] == 1:
                # Cycle detected
                has_cycle[0] = True
                return
        # Mark node as visited
        visited[node] = 2
        # Add node to the order
        order.append(node)