✅ 🎯 📌  Simple Solution  ||  Beats 83.9% in Time  ||  Topological Sort + Cycle Check  ✅ 🎯 📌
Approach\n Describe your approach to solving the problem. \nWe first apply topological sort algorithm on rowConditions and colConditions while simultaneously ch
# Approach\n<!-- Describe your approach to solving the problem. -->\nWe first apply topological sort algorithm on rowConditions and colConditions while simultaneously checking for cycles in these arrays.\nIf cycle exists, we cannot fulfill the conditions that make up the cycle \nand hence we return $$[\\ \\ ]$$.\nHowever if both topological sorts occur successfully, we now have row and col sequences that satisfy both rowCondition and colCondition and if we set the corresponding coordinate as the position at which it occurs in an array, \nthat is position in row topologically sorted sequence as row index and position in col topologically sorted sequence as col index, \nand we set those coordinates in the as grid as that number while setting the rest as 0, \nwe get the desired grid.\n\n# Code\n```\nclass Solution:\n    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n        rows,cols=defaultdict(list),defaultdict(list)\n        for i in rowConditions: rows[i[0]].append(i[1])\n        for i in colConditions: cols[i[0]].append(i[1])\n        def topological_sort_and_cycle_check(x,pars,arr):\n            visited[x]=1\n            path.append(x)\n            for i in arr[x]:\n                if i in path: return False \n                if visited[i]==0:\n                    if not topological_sort_and_cycle_check(i,pars|{x},arr): return False\n            stck.append(x)\n            path.pop()\n            return True\n\n        stck,path=[],[]\n        visited=[0 for i in range(k+1)]\n        for i in range(1,k+1): \n            path.append(i)\n            if visited[i]==0:\n                if not topological_sort_and_cycle_check(i,set([i]),rows): return []\n            path.pop()\n        rowtopsorted=stck[::-1]\n        \n        stck,path=[],[]\n        visited=[0 for i in range(k+1)]\n        for i in range(1,k+1): \n            path.append(i)\n            if visited[i]==0:\n                if not topological_sort_and_cycle_check(i,set([i]),cols): return []\n            path.pop()\n        coltopsorted=stck[::-1]\n        \n        coords={i:[0,0] for i in range(1,k+1)}\n        ans=[[0 for i in range(k)] for j in range(k)]\n        for i,j in enumerate(rowtopsorted): coords[j][0]=i\n        for i,j in enumerate(coltopsorted): coords[j][1]=i\n        for i in coords: ans[coords[i][0]][coords[i][1]]=i\n        return ans\n```
['Array', 'Graph', 'Topological Sort', 'Matrix', 'Python3']