Graph solution and runtime beats 97.22% [EXPLAINED]
IntuitionWe are given conditions that specify the relative positions of numbers in a matrix, both row-wise and column-wise. The goal is to arrange numbers such
# Intuition
We are given conditions that specify the relative positions of numbers in a matrix, both row-wise and column-wise. The goal is to arrange numbers such that these conditions are satisfied while filling a k x k matrix.

# Approach
Treat the row and column conditions as directed graphs and perform topological sorting on them to find a valid order for rows and columns, then place each number according to that order in the matrix.
This solution uses a graph to represent the conditions. Each condition (like "number a should be above number b in a row") forms a directed edge from a to b. The goal is to find a topological sort of the graph, which ensures that all conditions are satisfied, meaning numbers appear in the correct order in both rows and columns.

# Complexity
- Time complexity:
O(n + m + k), where n and m are the lengths of row and column conditions, and k is the size of the matrix.

- Space complexity:
O(k + n + m), as we store the graph, in-degree arrays, and topological orders.

# Code
```python3 []
class Solution:
    def buildMatrix(self, k: int, rowConditions: list[list[int]], colConditions: list[list[int]]) -> list[list[int]]:
        
        # Helper function to perform topological sorting using Kahn's algorithm
        def topological_sort(conditions, k):
            graph = defaultdict(list)
            in_degree = [0] * (k + 1)
            
            # Build graph and in-degree array
            for u, v in conditions:
                graph[u].append(v)
                in_degree[v] += 1
            
            # Queue for nodes with in-degree of 0
            queue = deque([i for i in range(1, k + 1) if in_degree[i] == 0])
            order = []
            
            while queue:
                node = queue.popleft()
                order.append(node)
                for neighbor in graph[node]:
                    in_degree[neighbor] -= 1
                    if in_degree[neighbor] == 0:
                        queue.append(neighbor)
            
            # If the order does not contain all elements, a cycle exists
            return order if len(order) == k else []
        
        # Get the topological order for row and column conditions
        row_order = topological_sort(rowConditions, k)
        col_order = topological_sort(colConditions, k)
        
        # If no valid order exists, return an empty matrix
        if not row_order or not col_order:
            return []
        
        # Create an empty k x k matrix
        matrix = [[0] * k for _ in range(k)]
        
        # Map each number to its row and column position
        row_pos = {num: idx for idx, num in enumerate(row_order)}
        col_pos = {num: idx for idx, num in enumerate(col_order)}
        
        # Fill the matrix
        for num in range(1, k + 1):
            matrix[row_pos[num]][col_pos[num]] = num
        
        return matrix

```
['Array', 'Graph', 'Topological Sort', 'Matrix', 'Python3']