You are given a positive integer k. You are also given:
a 2D integer array rowConditions of size n where rowConditions[i] = [above_i, below_i], and
a 2D integer array colConditions of size m where colConditions[i] = [left_i, right_i].
The two arrays contain integers from 1 to k.You have to build a k x k matrix that contains each of the numbers from 1 to kexactly once. The remaining cells should have the value 0.The matrix should also satisfy the following conditions:
The number above_i should appear in a row that is strictly above the row at which the number below_i appears for all i from 0 to n - 1.
The number left_i should appear in a column that is strictly left of the column at which the number right_i appears for all i from 0 to m - 1.
Return any matrix that satisfies the conditions. If no answer exists, return an empty matrix.
Input: k = 3, rowConditions = [[1,2],[3,2]], colConditions = [[2,1],[3,2]]Output: [[3,0,0],[0,0,1],[0,2,0]]Explanation: The diagram above shows a valid example of a matrix that satisfies all the conditions.The row conditions are the following:- Number 1 is in row 1, and number 2 is in row 2, so 1 is above 2 in the matrix.- Number 3 is in row 0, and number 2 is in row 2, so 3 is above 2 in the matrix.The column conditions are the following:- Number 2 is in column 1, and number 1 is in column 2, so 2 is left of 1 in the matrix.- Number 3 is in column 0, and number 2 is in column 1, so 3 is left of 2 in the matrix.Note that there may be multiple correct answers.
Input: k = 3, rowConditions = [[1,2],[2,3],[3,1],[2,3]], colConditions = [[2,1]]Output: []Explanation: From the first two conditions, 3 has to be below 1 but the third conditions needs 3 to be above 1 to be satisfied.No matrix can satisfy all the conditions, so we return the empty matrix.
from collections import defaultdict, dequeclass Solution: # Time: O(k + n + m) # Space: O(k + n + m) def build_matrix( self, k: int, row_conditions: list[list[int]], col_conditions: list[list[int]] ) -> list[list[int]]: def topological_order(conditions: list[list[int]]) -> list[int]: graph: dict[int, list[int]] = defaultdict(list) indegree = [0] * (k + 1) for above, below in conditions: graph[above].append(below) indegree[below] += 1 queue = deque(node for node in range(1, k + 1) if indegree[node] == 0) order: list[int] = [] while queue: node = queue.popleft() order.append(node) for neighbor in graph[node]: indegree[neighbor] -= 1 if indegree[neighbor] == 0: queue.append(neighbor) return order if len(order) == k else [] row_order = topological_order(row_conditions) if not row_order: return [] col_order = topological_order(col_conditions) if not col_order: return [] column_index = {number: idx for idx, number in enumerate(col_order)} matrix = [[0] * k for _ in range(k)] for row, number in enumerate(row_order): matrix[row][column_index[number]] = number return matrix
