Topological Sort | DFS | Python
Complexity\n- Time complexity: O(max(k^2,k+n,k+m)) where n=len(rowConditions) ,m = len(colConditions)\n\n- Space complexity: O(max(k^2,k+n,k+m))\n\n# Code\n\ncl
# Complexity\n- Time complexity: O(max(k^2,k+n,k+m)) where n=len(rowConditions) ,m = len(colConditions)\n\n- Space complexity: O(max(k^2,k+n,k+m))\n\n# Code\n```\nclass Solution:\n    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n        rowGraph,colGraph = defaultdict(list),defaultdict(list)\n\n        for a,b in rowConditions: #O(n)\n            rowGraph[b].append(a)\n\n        for l,r in colConditions: #O(m)\n            colGraph[r].append(l)\n\n        def dfs(num,graph,visited,res):\n            if num in visited:\n                return visited[num]\n            \n            visited[num] = True\n            for nei in graph[num]:\n                if dfs(nei,graph,visited,res):\n                    return True\n            visited[num] = False\n            res.append(num)\n\n        rowOrder,colOrder = [],[]\n        rowVisited,colVisited = {},{}\n        for i in range(1,k+1): #O(k+(m+n))\n            if dfs(i,rowGraph,rowVisited,rowOrder) or dfs(i,colGraph,colVisited,colOrder):\n                return []\n\n        colPos = defaultdict(int)\n        for i,num in enumerate(colOrder):#O(k)\n            colPos[num] = i\n\n        matrix = [[0 for i in range(k)] for j in range(k)] #O(k^2)\n\n        for index,r in enumerate(rowOrder):#O(k)\n            j = colPos[r]\n            matrix[index][j] = r\n        \n        return matrix\n\n\n\n```
['Array', 'Graph', 'Topological Sort', 'Matrix', 'Python', 'Python3']