Build a Matrix With Conditions
Intuition\n Describe your first thoughts on how to solve this problem. \nTo construct a k x k matrix that satisfies the given row and column conditions, we need
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo construct a k x k matrix that satisfies the given row and column conditions, we need to determine a valid order for placing numbers in rows and columns. This can be achieved by treating the conditions as a dependency graph and ensuring the order constraints are met.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n#### 1. Graph Representation:\n - Use adjacency lists to represent row and column conditions.\n - Use an indegree dictionary to keep track of incoming edges for each node.\n#### 2. Order Calculation:\n - Apply a queue-based method to determine a valid order for rows and columns. This ensures that all conditions are met.\n#### 3. Matrix Construction:\n - Construct the matrix using the determined row and column orders by placing each number at its respective position.\n# Complexity\n- Time complexity: $$O(n)^2$$ due to the iteration over all nodes and processing each edge.\n- Space complexity: $$O(n)^2$$ to store the graph and indegree information\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nfrom collections import defaultdict, deque\n\nclass Solution:\n    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n        # Function to build a graph and compute indegrees from conditions\n        def build_graph(conditions):\n            graph = defaultdict(set)  # Adjacency list representation of the graph\n            indegree = defaultdict(int)  # Dictionary to count incoming edges\n            for u, v in conditions:\n                if v not in graph[u]:  # Avoid adding duplicate edges\n                    graph[u].add(v)\n                    indegree[v] += 1\n            return graph, indegree\n\n        # Function to calculate a valid order using Kahn\'s Algorithm\n        def calculate_order(graph, indegree, k):\n            order = []\n            queue = deque([i for i in range(1, k + 1) if indegree[i] == 0])  # Nodes with zero incoming edges\n            while queue:\n                node = queue.popleft()\n                order.append(node)\n                for neighbor in graph[node]:\n                    indegree[neighbor] -= 1  # Decrement indegree of the neighbor\n                    if indegree[neighbor] == 0:\n                        queue.append(neighbor)  # Add nodes with zero indegree to the queue\n            return order if len(order) == k else []  # Check if we got a valid order\n\n        # Build graphs and calculate orders for rows and columns\n        row_graph, row_indegree = build_graph(rowConditions)\n        col_graph, col_indegree = build_graph(colConditions)\n        \n        row_order = calculate_order(row_graph, row_indegree, k)\n        col_order = calculate_order(col_graph, col_indegree, k)\n        \n        if not row_order or not col_order:\n            return []  # Return an empty matrix if we cannot satisfy the conditions\n        \n        # Create mappings from number to its position in the order\n        row_pos = {num: i for i, num in enumerate(row_order)}\n        col_pos = {num: i for i, num in enumerate(col_order)}\n\n        # Initialize an empty k x k matrix\n        matrix = [[0] * k for _ in range(k)]\n        # Fill the matrix based on row and column positions\n        for num in range(1, k + 1):\n            matrix[row_pos[num]][col_pos[num]] = num\n\n        return matrix  # Return the constructed matrix\n\n\n```
['Array', 'Graph', 'Topological Sort', 'Matrix', 'Python3']