Topological sort using DFS & Kahn's algorithm + optimizations.
All we need is to sort rows and cols dependencies in topological order. If we look at provided example Input: k = 3, rowConditions = [[1,2],[3,2]], colCondition
All we need is to sort rows and cols dependencies in topological order. If we look at provided example Input: k = 3, rowConditions = [[1,2],[3,2]], colConditions = [[2,1],[3,2]] we can see, that if we construct graphs for rows&cols conditions and then sort vertices of those graphs in topological order we would have next sorted arrays of vertices: 3, 1, 2 for rows and 3, 2, 1 for cols. Then we can use indexes of each element in those sorted arrays as coords in result matrix. Belows is 2 solutions based on DFS topological sorting. First is more intuitive, second one is the same, but memory and speed optimized.\n\n# Code\n```\nclass Solution {\npublic:\n    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {\n        vector<vector<short>> rowsGraph(k+1);\n        vector<vector<short>> colsGraph(k+1);\n\n        for (auto& condition : rowConditions)\n            rowsGraph[condition[1]].push_back(condition[0]);\n\n        for (auto& condition : colConditions)\n            colsGraph[condition[1]].push_back(condition[0]);\n\n        vector<char> visited(k+1);\n        vector<short> rowsSort;\n        vector<short> colsSort;\n        rowsSort.reserve(k);\n        colsSort.reserve(k);\n\n        for (short i = 1; i <= k; i++)\n            if (!topoSort(rowsGraph, visited, rowsSort, i, 2) || !topoSort(colsGraph, visited, colsSort, i, 4))\n                return {};\n\n        vector<vector<int>> matrix(k, vector<int>(k));\n        vector<pair<short, short>> coords(k+1);\n        for (short i = 0; i < rowsSort.size(); i++) {\n            coords[rowsSort[i]].first = i;\n            coords[colsSort[i]].second = i;\n        }\n\n        for (short i = 1; i <= k; i++)\n            matrix[coords[i].first][coords[i].second] = i;\n\n        return matrix;\n    }\n\n    bool topoSort(vector<vector<short>>& graph, vector<char>& visited, vector<short>& sorted, short vertice, char flag) {\n        // Cycle detection\n        if (visited[vertice] & 1)\n            return false;\n\n        if (visited[vertice] & flag)\n            return true;\n\n        visited[vertice] |= flag + 1;\n        for (short parent : graph[vertice])\n            if (!topoSort(graph, visited, sorted, parent, flag))\n                return false;\n\n        sorted.push_back(vertice);\n        visited[vertice] -= 1;\n        return true;\n    }\n};\n\n```\nOptimized solution without extra arrays for topological sorting.\n```\nclass Solution {\npublic:\n    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {\n        vector<vector<short>> rowsGraph(k+1);\n        vector<vector<short>> colsGraph(k+1);\n\n        // Build rows dependencies graph\n        for (auto& condition : rowConditions)\n            rowsGraph[condition[1]].push_back(condition[0]);\n\n        // Build cols dependencies graph\n        for (auto& condition : colConditions)\n            colsGraph[condition[1]].push_back(condition[0]);\n\n        // Single array to track visited rows & cols.\n        // Instead of using 2 arrays of bools we can use array of chars and mark visited by adding binary flag\n        // Flag 2 for rows and flag 4 for cols, there also gonna be flag 1 for cycle detection\n        vector<char> visited(k+1);\n        // In those arrays we gonna track ay which index row,col should appear each 1..k element\n        // To find those indexes properly we gonna use modified topological sort by DFS\n        // In overall row & col coords is appropriate index of element in rows/cols topological sort\n        // Lets assume that after topological sorting elements in graph we would have 2 sorted arrays: 3, 1, 2 for rows and 3, 2, 1 for cols\n        // We can see that index in sorted array of each element is its row&col coord in matrix\n        // To save momery and speed we can emulate togological sorting using references to rowIndex & colIndex\n        vector<short> rowIndexes(k+1);\n        vector<short> colIndexes(k+1);\n        short rowIndex = 0, colIndex = 0;\n\n        // Sort topologically graphs of rows and cols\n        for (short i = 1; i <= k; i++)\n            if (!topoSort(rowsGraph, visited, rowIndexes, rowIndex, i, 2) || !topoSort(colsGraph, visited, colIndexes, colIndex, i, 4))\n                return {};\n\n        vector<vector<int>> matrix(k, vector<int>(k));\n        for (short i = 1; i <= k; i++)\n            matrix[rowIndexes[i]][colIndexes[i]] = i;\n\n        return matrix;\n    }\n\n    bool topoSort(vector<vector<short>>& graph, vector<char>& visited, vector<short>& indexes, short& index, short vertice, char flag) {\n        // Cycle detection, check if we reached same vertice in single DFS run\n        if (visited[vertice] & 1)\n            return false;\n\n        if (visited[vertice] & flag)\n            return true;\n\n        // Mark vertice as visited, also add flag 1 for cycle detection\n        visited[vertice] |= flag | 1;\n        for (short parent : graph[vertice])\n            if (!topoSort(graph, visited, indexes, index, parent, flag))\n                return false;\n\n        // Set index of vertice in togological order\n        indexes[vertice] = index++;\n        // Remove cycle detection flag\n        visited[vertice] &= ~1;\n        return true;\n    }\n};\n\n```\n\nSame idea but using Kahn\'s algorithm for topological sort:\n```\nclass Solution {\npublic:\n    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {\n        vector<short> rowIndexes(k+1);\n        vector<short> colIndexes(k+1);\n\n        if (!topoSort(k, rowConditions, rowIndexes) || !topoSort(k, colConditions, colIndexes))\n            return {};\n\n        vector<vector<int>> matrix(k, vector<int>(k));\n        for (short i = 1; i <= k; i++)\n            matrix[rowIndexes[i]][colIndexes[i]] = i;\n\n        return matrix;\n    }\n\n    bool topoSort(int k, vector<vector<int>>& edges, vector<short>& indexes) {\n        vector<vector<short>> graph(k+1);\n        vector<short> indegree(graph.size());\n        queue<short> vertices;\n\n        for (auto& edge : edges) {\n            graph[edge[0]].push_back(edge[1]);\n            indegree[edge[1]]++;\n        }\n\n        for (short vertex = 1; vertex < graph.size(); vertex++)\n            if (indegree[vertex] == 0)\n                vertices.push(vertex);\n\n        short index = 0;\n        while (!vertices.empty()) {\n            short vertex = vertices.front();\n            indexes[vertex] = index++;\n            vertices.pop();\n\n            for (short next : graph[vertex])\n                if (--indegree[next] == 0)\n                    vertices.push(next);\n        }\n\n        return index == indexes.size()-1;\n    }\n};\n```\n
['C++']