✅Beats 100% || Made it easy for you || C++/Java/Python/JS || Topological Sort || Explained in Detail
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem is about arranging integers from 1 to \uD835\uDC58\nk in a \uD835\uDC58 \xD
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem is about arranging integers from 1 to \uD835\uDC58\nk in a \uD835\uDC58 \xD7 \uD835\uDC58 matrix such that: \n1. Specific integers appear in certain rows (based on rowConditions).\n2. Specific integers appear in certain columns (based on colConditions).\nThe constraints imply a topological sorting problem, where we need to arrange elements based on dependencies. We need to ensure that no circular dependencies exist (otherwise, the arrangement is impossible).\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Graph Construction:**\n    - Build two directed graphs (rowGraph and colGraph) based on rowConditions and colConditions, respectively.\n    - Each graph represents dependencies (edges) between elements (nodes).\n\n2. **Topological Sorting:**\n    - Perform topological sorting on both graphs.\n    - If topological sorting fails (cycle detected), return an empty matrix because it\'s impossible to arrange the integers.\n\n3. **Matrix Construction:**\n    - Use the results of topological sorts to determine the row and column positions of each integer.\n    - Construct the final matrix based on these positions.\n\n# Complexity\n- Time complexity:\n    - Constructing graphs: $$\uD835\uDC42(\uD835\uDC5F+\uD835\uDC50)$$, where \uD835\uDC5F is the number of rowConditions and \uD835\uDC50 is the number of colConditions.\n    - Topological sorting: $$O(k+r)+O(k+c)$$ (for row and column graphs respectively).\n    - Building the result matrix: $$O(k).$$\nOverall time complexity: $$O(k+r+c).$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n    - Graph storage: O(k + n) for rows and O(k + m) for columns.\n    - Additional space for topological sorting: O(k).\n    - Matrix storage: O(k^2).\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n# Example\n**Input**\n-  k = 3\n- rowConditions = [[1, 2], [2, 3]]\n    - colConditions = [[2, 1], [3, 2]]\n\n**Step-by-Step Solution**\n\n1. **Graph Construction:**\n    - rowGraph:\n        - 1 -> 2\n        - 2 -> 3\n    - colGraph:\n        - 2 -> 1\n        - 3 -> 2\n\n2. **Topological Sorting**:\n    - Topological sort on rowGraph:\n        - Start with 1 (in-degree 0), then 2, then 3.\n        - rowOrder = [1, 2, 3].\n    - Topological sort on colGraph:\n        - Start with 3 (in-degree 0), then 2, then 1.\n        - colOrder = [3, 2, 1].\n\n3. **Mapping Positions:**\n    - rowMap:\n        - 1 -> row 0\n        - 2 -> row 1\n        - 3 -> row 2\n    - colMap:\n        - 3 -> col 0\n        - 2 -> col 1\n        - 1 -> col 2\n\n4. **Matrix Construction:**\n    - Position 1 at (0, 2)\n    - Position 2 at (1, 1)\n    - Position 3 at (2, 0)\n\n5. **Final matrix:**\n```\n[[0, 0, 1],\n [0, 2, 0],\n [3, 0, 0]]\n\n```\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {\n        vector<vector<int>> rowGraph(k + 1), colGraph(k + 1);\n        for (auto& rc : rowConditions) {\n            rowGraph[rc[0]].push_back(rc[1]);\n        }\n        for (auto& cc : colConditions) {\n            colGraph[cc[0]].push_back(cc[1]);\n        }\n        \n        vector<int> rowOrder = topoSort(rowGraph, k);\n        vector<int> colOrder = topoSort(colGraph, k);\n        \n        if (rowOrder.empty() || colOrder.empty()) return {};\n        \n        vector<vector<int>> result(k, vector<int>(k, 0));\n        unordered_map<int, int> rowMap, colMap;\n        for (int i = 0; i < k; ++i) {\n            rowMap[rowOrder[i]] = i;\n            colMap[colOrder[i]] = i;\n        }\n        \n        for (int i = 1; i <= k; ++i) {\n            result[rowMap[i]][colMap[i]] = i;\n        }\n        \n        return result;\n    }\n    \n    vector<int> topoSort(vector<vector<int>>& graph, int k) {\n        vector<int> inDegree(k + 1, 0), order;\n        queue<int> q;\n        for (int i = 1; i <= k; ++i) {\n            for (int j : graph[i]) {\n                ++inDegree[j];\n            }\n        }\n        for (int i = 1; i <= k; ++i) {\n            if (inDegree[i] == 0) q.push(i);\n        }\n        while (!q.empty()) {\n            int node = q.front(); q.pop();\n            order.push_back(node);\n            for (int adj : graph[node]) {\n                if (--inDegree[adj] == 0) q.push(adj);\n            }\n        }\n        return order.size() == k ? order : vector<int>();\n    }\n};\n```\n```python []\nclass Solution(object):\n    def buildMatrix(self, k, rowConditions, colConditions):\n        rowGraph = defaultdict(list)\n        for u, v in rowConditions:\n            rowGraph[u].append(v)\n            \n        colGraph = defaultdict(list)\n        for u, v in colConditions:\n            colGraph[u].append(v)\n        \n        def topoSort(graph):\n            inDegree = {i: 0 for i in range(1, k + 1)}\n            for u in graph:\n                for v in graph[u]:\n                    inDegree[v] += 1\n            queue = deque([i for i in inDegree if inDegree[i] == 0])\n            order = []\n            while queue:\n                node = queue.popleft()\n                order.append(node)\n                for v in graph[node]:\n                    inDegree[v] -= 1\n                    if inDegree[v] == 0:\n                        queue.append(v)\n            return order if len(order) == k else []\n        \n        rowOrder = topoSort(rowGraph)\n        colOrder = topoSort(colGraph)\n        \n        if not rowOrder or not colOrder:\n            return []\n        \n        rowMap = {num: i for i, num in enumerate(rowOrder)}\n        colMap = {num: i for i, num in enumerate(colOrder)}\n        \n        result = [[0] * k for _ in range(k)]\n        for i in range(1, k + 1):\n            result[rowMap[i]][colMap[i]] = i\n        \n        return result\n        \n```\n```java []\nclass Solution {\n    public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {\n        List<Integer>[] rowGraph = new ArrayList[k + 1]; \n        for(int i = 1 ; i < rowGraph.length; i ++) {\n            rowGraph[i] = new ArrayList();\n        }\n        for(int [] rowCondition : rowConditions){ \n            rowGraph[rowCondition[0]].add(rowCondition[1]); \n        }\n\n        List<Integer>[] colGraph = new ArrayList[k + 1]; \n        for(int i = 1 ; i < colGraph.length; i ++) {\n            colGraph[i] = new ArrayList();\n        }\n        for(int [] colCondition : colConditions){\n            colGraph[colCondition[0]].add(colCondition[1]); \n        }\n\n        int[] visited = new int[k + 1];\n        Deque<Integer> queue = new LinkedList<>(); \n        for(int i = 1; i < rowGraph.length; i++){ \n            if(!topSort(rowGraph, i, visited, queue)){\n                return new int[0][0];\n            }\n        }\n\n        \n        int[] rowIndexMap = new int[k + 1]; \n        for(int i = 0; i < k; i++){ \n            int node = queue.pollLast(); \n            rowIndexMap[node] = i;\n        }\n\n        visited = new int[k + 1];\n        queue = new LinkedList();\n        for(int i = 1; i < colGraph.length; i++){\n            if(!topSort(colGraph, i, visited, queue)){\n                return new int[0][0];\n            }\n        }\n\n        int[] colOrder = new int[k];\n        int[] colIndexMap = new int[k+1];\n        for(int i = 0; i < k; i++){\n            int node = queue.pollLast();\n            colOrder[i] = node;\n            colIndexMap[node] = i;\n        }\n\n        int[][] result = new int[k][k];\n        \n        for(int i = 1; i <= k; i++){\n            result[rowIndexMap[i]][colIndexMap[i]] = i;\n        }\n\n        return result;\n\n    }\n\n    public boolean topSort(List<Integer>[] graph, int node, int[] visited, Deque<Integer> queue){\n        if(visited[node] == 2) {\n            return false;\n        }\n        if(visited[node] == 0){\n            visited[node] = 2;\n            for(int child : graph[node]){\n                if(!topSort(graph, child, visited, queue)){\n                    return false;\n                }\n            }\n            visited[node] = 1;\n            queue.add(node);\n        }\n        return true;\n    }\n}\n```\n``` javascript []\n/**\n * @param {number} k\n * @param {number[][]} rowConditions\n * @param {number[][]} colConditions\n * @return {number[][]}\n */\nvar buildMatrix = function(k, rowConditions, colConditions) {\n    \nconst rowGraph = Array.from({ length: k + 1 }, () => []);\n    const colGraph = Array.from({ length: k + 1 }, () => []);\n    \n    for (const [u, v] of rowConditions) {\n        rowGraph[u].push(v);\n    }\n    for (const [u, v] of colConditions) {\n        colGraph[u].push(v);\n    }\n    \n    const topoSort = (graph) => {\n        const inDegree = Array(k + 1).fill(0);\n        for (const u of graph) {\n            for (const v of u) {\n                inDegree[v]++;\n            }\n        }\n        const queue = [];\n        for (let i = 1; i <= k; i++) {\n            if (inDegree[i] === 0) queue.push(i);\n        }\n        const order = [];\n        while (queue.length) {\n            const node = queue.shift();\n            order.push(node);\n            for (const v of graph[node]) {\n                if (--inDegree[v] === 0) queue.push(v);\n            }\n        }\n        return order.length === k ? order : [];\n    };\n    \n    const rowOrder = topoSort(rowGraph);\n    const colOrder = topoSort(colGraph);\n    \n    if (!rowOrder.length || !colOrder.length) return [];\n    \n    const rowMap = rowOrder.reduce((acc, num, i) => {\n        acc[num] = i;\n        return acc;\n    }, {});\n    \n    const colMap = colOrder.reduce((acc, num, i) => {\n        acc[num] = i;\n        return acc;\n    }, {});\n    \n    const result = Array.from({ length: k }, () => Array(k).fill(0));\n    for (let i = 1; i <= k; i++) {\n        result[rowMap[i]][colMap[i]] = i;\n    }\n    \n    return result;\n};\n```\n![upvote.png](https://assets.leetcode.com/users/images/c5eee41c-cfe4-41bb-81ef-cbbb39ad4ab8_1721539802.0814426.png)\n\n
['Array', 'Graph', 'Topological Sort', 'Matrix', 'Python', 'C++', 'Java', 'JavaScript']