Build a Matrix With Conditions Python Solution

lcpy gen -n 2392   # by problem number
lcpy gen -s build_a_matrix_with_conditions   # by problem name

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, deque


class 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