[Python] Topological Sort Explained
rows and cols are independent, just run 2 topological sorts on each direction. time complexity is O(k^2)\n\n\nclass Solution:\n    def buildMatrix(self, k: int,
rows and cols are independent, just run 2 topological sorts on each direction. time complexity is O(k^2)\n\n```\nclass Solution:\n    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n        res = [[0 for _ in range(k)] for _ in range(k)]\n        \n        # build 2 graphs for row and col independently, count indegrees for each node \n        # a node in each graph is a number between 1 to k\n        row_graph, col_graph = defaultdict(set), defaultdict(set)\n        row_indegrees, col_indegrees = defaultdict(int), defaultdict(int)\n        for i, j in rowConditions:\n            # note the input conditions could contain duplicates\n            if j not in row_graph[i]:\n                row_graph[i].add(j)\n                row_indegrees[j] += 1\n        for i, j in colConditions:\n            if j not in col_graph[i]:\n                col_graph[i].add(j)\n                col_indegrees[j] += 1\n        \n        # run topological sort for nodes in row graph\n        row_queue, col_queue = deque(), deque()\n        row_order, col_order = {}, {}\n        row_order_counter, col_order_counter = 0, 0\n        row_visited, col_visited = set(), set()\n        for i in range(1, k+1):\n            # note that numbers did not appear in row conditions also have row_indegree = 0\n            if row_indegrees[i] == 0:\n                row_queue.append(i)\n                row_visited.add(i)\n        while row_queue:\n            cur = row_queue.popleft()\n            row_order[cur] = row_order_counter\n            row_order_counter += 1\n            for nxt in row_graph[cur]:\n                if nxt in row_visited:\n                    continue\n                row_indegrees[nxt] -= 1\n                if row_indegrees[nxt] <= 0:\n                    row_visited.add(nxt)\n                    row_queue.append(nxt)\n        \n        # same topological sort for col graph\n        for i in range(1, k+1):\n            if col_indegrees[i] == 0:\n                col_queue.append(i)\n                col_visited.add(i)\n        while col_queue:\n            cur = col_queue.popleft()\n            col_order[cur] = col_order_counter\n            col_order_counter += 1\n            for nxt in col_graph[cur]:\n                if nxt in col_visited:\n                    continue\n                col_indegrees[nxt] -= 1\n                if col_indegrees[nxt] <= 0:\n                    col_visited.add(nxt)\n                    col_queue.append(nxt)\n\n        # check if either row conditions or col conditions contains cycle\n        if not (len(row_order) == k and len(col_order) == k):\n            return []\n        \n        # no cycle, build result with row and col independently\n        for i in range(1, k+1):\n            res[row_order[i]][col_order[i]] = i\n        return res\n            \n        \n            \n        \n```
[]