Topological sorting | Kahn's algorithm
We have hierarchy given to us by rowConditions and colConditions. We can map that hierarchy with a topological ordering algorithm.\n\nLet\'s find the order we c
We have hierarchy given to us by rowConditions and colConditions. We can map that hierarchy with a topological ordering algorithm.\n\nLet\'s find the order we can place rows and columns separately by running the Kahn\'s topsort algorithm. If there is a cycle detected we know we cannot have a valid order, we return `[]` as required.\n\nOtherwise we have a valid order, so for every node `[1,k]` we look it\'s index position in the rows order and cols order and put it in the matrix.\n\n```\nclass Solution:\n    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n        try:\n            row_conditions_topsort, row_node_to_index = self.top_sort(k, rowConditions)\n            col_conditions_topsort, col_node_to_index = self.top_sort(k, colConditions)\n            matrix = [[0 for _ in range(k)] for _ in range(k)]\n            \n            for n in range(1, k + 1):\n                row, col = row_node_to_index[n], col_node_to_index[n]\n                matrix[row][col] = n\n            \n            return matrix\n            \n            \n        except:\n            # If error thrown, kahn\'s algorithm detected a cycle\n            return []\n        \n    def top_sort(self, k, edges: tuple[int, int]) -> list[int]:\n        indegree = defaultdict(int)\n        graph = defaultdict(list)\n        \n        for n in range(1, k + 1):\n            indegree[n] = 0\n        \n        for u, v in edges:\n            graph[u].append(v)\n            indegree[v] += 1\n        \n        queue = deque()\n        topsort = []\n        for n in range(1, k + 1):\n            if indegree[n] == 0:\n                queue.append(n)\n        \n        while queue:\n            node = queue.popleft()\n            topsort.append(node)\n            \n            for nei in graph[node]:\n                indegree[nei] -= 1\n                if indegree[nei] == 0:\n                    queue.append(nei)\n        \n        if len(topsort) != k:\n            raise Exception()\n        \n        node_to_index = {}\n        for i, n in enumerate(topsort):\n            node_to_index[n] = i\n        \n        return topsort, node_to_index\n```\n\n\n<hr />\nTook the virtual contest today :).\n\n<img src="https://nadarsandbox-videocontent-sandbox.s3.amazonaws.com/raw-thumbnails/WhatsApp+Image+2022-08-28+at+11.48.29+AM.jpeg" />
['Python']