Easy Solution | Topological Sort | Python | C++
Approach\n1. Initialize and Populate the Graphs for rows and Columns:\n2. then create a topological sort function that sorts the given action in such a order th
# Approach\n1. Initialize and Populate the Graphs for rows and Columns:\n2. then create a topological sort function that sorts the given action in such a order that if theres a dependency of child over a parent then child will always come after the parent. \n    - Create a stack deque(why deque becuse it will help us append at 0 index in O(1) complexity whereas a normal list will take O(N) in worst time), visited set, check_cycle set and a 0 indexed cycle list defaulted at False ( will be update to True if found a cycle)\n    - define a topoLogical_sort_helper function (in our case it is topoHelper) which is doing  a recursive DFS in our topologicalsort function as well as checking for possible cycles.\n\n3. get the topological order of rows and columns using topologicalsort function.\n4. check wheather there is a cycle or not by checking wheather a valid rows and column are returned by the function.\n5. create a new dictionary d to store the indexed value of our row Position as it help us reduce the time for search of index in rows.\n6. update the matrix and then return it.\n\n# Complexity\n- Time complexity: O(N + M)\n\n- Space complexity: O(N + M)\n\n# Code\n```python []\nclass Solution(object):\n    def buildMatrix(self, k, rowConditions, colConditions):\n        rowgraph = defaultdict(list)\n        colgraph = defaultdict(list)\n\n        for x in rowConditions:\n            rowgraph[x[0]].append(x[1])\n        for x in colConditions:\n            colgraph[x[0]].append(x[1])\n        \n        def topologicalsort(graph):\n            stack = deque()\n            visited = set()\n            check_cycle = set()\n            cycle = [False]\n\n            def topoHelper(x):\n                if cycle[0]:\n                    return\n\n                visited.add(x)\n                check_cycle.add(x)\n                for i in graph[x]:\n                    if i in check_cycle:\n                        cycle[0] = True\n                        return\n\n                    if i not in visited:\n                        topoHelper(i)\n                check_cycle.remove(x)\n                stack.appendleft(x)\n            \n            for i in range(1,k+1):\n                if cycle[0]:\n                    return []\n\n                if i not in visited:\n                    topoHelper(i)\n            return list(stack)\n        \n        rows = topologicalsort(rowgraph)\n        columns = topologicalsort(colgraph)\n\n        if not rows or not columns:\n            return []\n\n        d = {}\n        for i,x in enumerate(rows):\n            d[x] = i\n        \n        matrix = [[0]*k for _ in range(k)]\n        for i,x in enumerate(columns):\n            matrix[d[x]][i] = x\n        return matrix\n```\n```C++ []\nclass Solution {\npublic:\n    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {\n        unordered_map<int, vector<int>> rowgraph;\n        unordered_map<int, vector<int>> colgraph;\n\n        for (const auto& x : rowConditions) {\n            rowgraph[x[0]].push_back(x[1]);\n        }\n        for (const auto& x : colConditions) {\n            colgraph[x[0]].push_back(x[1]);\n        }\n\n        auto topologicalsort = [&](unordered_map<int, vector<int>>& graph) {\n            deque<int> stack;\n            unordered_set<int> visited;\n            unordered_set<int> check_cycle;\n            bool cycle = false;\n\n            function<void(int)> topoHelper = [&](int x) {\n                if (cycle) return;\n\n                visited.insert(x);\n                check_cycle.insert(x);\n                for (int i : graph[x]) {\n                    if (check_cycle.find(i) != check_cycle.end()) {\n                        cycle = true;\n                        return;\n                    }\n                    if (visited.find(i) == visited.end()) {\n                        topoHelper(i);\n                    }\n                }\n                check_cycle.erase(x);\n                stack.push_front(x);\n            };\n\n            for (int i = 1; i <= k; ++i) {\n                if (cycle) return vector<int>();\n                if (visited.find(i) == visited.end()) {\n                    topoHelper(i);\n                }\n            }\n            return vector<int>(stack.begin(), stack.end());\n        };\n\n        vector<int> rows = topologicalsort(rowgraph);\n        vector<int> columns = topologicalsort(colgraph);\n\n        if (rows.empty() || columns.empty()) {\n            return {};\n        }\n\n        unordered_map<int, int> d;\n        for (int i = 0; i < rows.size(); ++i) {\n            d[rows[i]] = i;\n        }\n\n        vector<vector<int>> matrix(k, vector<int>(k, 0));\n        for (int i = 0; i < columns.size(); ++i) {\n            matrix[d[columns[i]]][i] = columns[i];\n        }\n\n        return matrix;\n    }\n};\n```\n![unnamed.jpg](https://assets.leetcode.com/users/images/5cd2e930-9511-4569-9a58-349b087a3009_1721556533.832895.jpeg)\n\n
['Array', 'Graph', 'Topological Sort', 'Matrix', 'Python', 'C++', 'Python3']