Topological Sort with Explanation and Complexity Analysis
Rationale\n The row and column dependencies could be established with a directed graph, where any edge from vertex A to vertex B denotes that vertex A should co
##### Rationale\n* The row and column dependencies could be established with a directed graph, where any edge from vertex A to vertex B denotes that vertex A should come before vertex B in the matrix\n* To resolve the dependencies, we could sort them topologically\n* If the relationship is acyclic, we would have all the elements ordered. Otherwise, the sort would stop early (see Kahn\'s Algorithm) with elements less than k\n* Post the topological sort for both the dependencies, we could find out the required indexes for all the elements and put them in the matrix. Note that the index at which the candidate is present in the topological order for the row relationship would be its row index. The same goes for its column index\n\n##### Complexities\n* Time: `O(k * k)`\n* Space: `O(k * k)`\n\nThese are loose bounds based upon the fact that the runtime for the sort is `O(V + E)`. For this problem, `V = k`. In the worse case, `E` could be `(V * (V - 1)) / 2` or `(k * (k - 1)) / 2`. Thus, the total runtime would be `O(k + (k * k))` or `O(k * k)`. (Note that the other operations that we\'ve done come under `O(k * k)` as well.)\n\n```\nclass Solution:\n    def topological_sort(self, k: int, relations: List[List[int]]) -> List[int]:\n        graph = [[] for _ in range(k)]\n        indegrees = [0] * k\n        order = []\n        \n        for _from, to in items:\n            _from -= 1\n            to -= 1\n            \n            graph[_from].append(to)\n            indegrees[to] += 1\n\n        queue = deque([vertex for vertex in range(k) if ind[vertex] == 0])\n        \n        while queue:\n            curr = queue.popleft()\n            \n            order.append(curr)\n            \n            for neighbor in graph[curr]:     \n                indegrees[neighbor] -= 1\n                if indegrees[neighbor] == 0:\n                    queue.append(neighbor)\n                    \n        return order     \n        \n    def buildMatrix(self, k: int, rows: List[List[int]], cols: List[List[int]]) -> List[List[int]]:\n        topological_row = self.topological_sort(k, rows)\n        topological_col = self.topological_sort(k, cols)\n        \n        # The dependencies couldn\'t be resolved. Return early.\n        if len(top_row) != k or len(top_col) != k:\n            return []\n\n        # Based upon the relationships, find the row and column indices for every candidate.\n        indexes = defaultdict(list)\n        \n        for row_index, candidate in enumerate(topological_row):\n            indexes[candidate].append(row_index)\n            \n        for col_index, candidate in enumerate(topological_col):\n            indexes[candidate].append(col_index)\n        \n        # Build the required matrix.\n        matrix = [[0 for _ in range(k)] for __ in range(k)]\n        for num in range(k):\n            row, col = indexes[num]\n            matrix[row][col] = num + 1\n            \n        return matrix\n```\n
['Breadth-First Search', 'Topological Sort']