Python Topo Sort
Intuition\n Describe your first thoughts on how to solve this problem. \nUse topological sort to find the order of row and col\n\nIn the first example:\n\n[3,0,
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nUse topological sort to find the order of row and col\n\nIn the first example:\n```\n[3,0,0]\n[0,0,1]\n[0,2,0]\n```\nThe row order from top to bottom is `3 -> 1 -> 2`\nThe col order from left to right is `3 -> 2 -> 1`\n\nNow we know the position in (i, j) for each value [1, k]\nReturn an empty array if we can\'t build the matrix\n\n# Complexity\n- Time complexity: $$O(K * K)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(K * K)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python []\nclass Solution:\n    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n        \n        def order(conditions):\n            adj = [[] for _ in range(k + 1)]\n            deg = [0] * (k + 1)\n            for u, v in conditions:\n                adj[u].append(v)\n                deg[v] += 1\n\n            s = []\n            for u, d in enumerate(deg):\n                if u and d == 0:\n                    s.append(u)\n            \n            res = []\n            while s:\n                u = s.pop()\n                res.append(u)\n                for v in adj[u]:\n                    deg[v] -= 1\n                    if deg[v]:\n                        continue\n                    s.append(v)\n\n            if any(deg):\n                return []\n            return res\n\n            \n        row = order(rowConditions)\n        col = order(colConditions)\n        \n        col = {x: i for i, x in enumerate(col)}\n        res = [[0] * k for _ in range(k)]\n        for i, x in enumerate(row):\n            if x not in col:\n                break\n            j = col[x]\n            res[i][j] = x\n\n        for r in res:\n            if not any(r):\n                return []\n        return res\n\n```
['Python3']