✅Beats 100% -Explained with [ Video ] -C++/Java/Python/JS - Topological Sort - Explained in Detail
\n\n# YouTube Video Explanation:\n\n ### To watch the video please click on "Watch On Youtube" option  available the left bottom corner of the thumbnail. \n\nIf
![Screenshot 2024-07-21 062841.png](https://assets.leetcode.com/users/images/a31b23a1-85be-45d0-856c-369abd9fa85c_1721524294.9685822.png)\n\n# YouTube Video Explanation:\n\n<!-- ### To watch the video please click on "Watch On Youtube" option  available the left bottom corner of the thumbnail. -->\n\n**If you want a video for this question please write in the comments**\n\n\n<!-- https://youtu.be/h_YTOvo65ng -->\n\n\n**\uD83D\uDD25 Please like, share, and subscribe to support our channel\'s mission of making complex concepts easy to understand.**\n\nSubscribe Link: https://www.youtube.com/@leetlogics/?sub_confirmation=1\n\n*Subscribe Goal: 2700 Subscribers*\n*Current Subscribers: 2641*\n\nFollow me on Instagram : https://www.instagram.com/divyansh.nishad/\n\n---\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem can be viewed as a topological sorting problem. We need to order the rows and columns such that the conditions given in `rowConditions` and `colConditions` are met. This can be achieved by treating the conditions as directed edges in a graph and performing a topological sort.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Graph Construction**:\n   - Construct a graph for row conditions and another graph for column conditions.\n   - Nodes represent the numbers from 1 to k.\n   - Directed edges represent the conditions, e.g., `rowConditions[i] = [a, b]` implies an edge from `a` to `b`.\n\n2. **Topological Sorting**:\n   - Perform topological sorting on both graphs to determine the order of rows and columns.\n   - Use Depth First Search (DFS) for topological sorting and detect any cycles which would make it impossible to satisfy the conditions.\n\n3. **Matrix Construction**:\n   - Using the order obtained from the topological sort, place each number from 1 to k in the corresponding position in the k x k matrix.\n\n4. **Validation**:\n   - If any cycle is detected during the topological sorting, return an empty matrix as it indicates that it is impossible to satisfy all conditions.\n\n\n# Complexity\n- **Time Complexity**:\n  - Constructing the graph: O(n + m), where n and m are the lengths of `rowConditions` and `colConditions` respectively.\n  - Topological Sorting: O(k + n) for rows and O(k + m) for columns.\n  - Matrix construction: O(k^2).\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\n\n# Step-by-Step Explanation\n\n#### Step 1: Construct Graphs for Conditions\n\nWe\'ll construct two directed graphs:\n1. `rowGraph` for `rowConditions`\n2. `colGraph` for `colConditions`\n\n**Example Input:**\n- \\( k = 3 \\)\n- `rowConditions = [[1, 2], [3, 2]]`\n- `colConditions = [[2, 1], [3, 2]]`\n\n**Row Graph:**\n\n| Node | Edges   |\n|------|---------|\n| 1    | [2]     |\n| 3    | [2]     |\n\n**Column Graph:**\n\n| Node | Edges   |\n|------|---------|\n| 2    | [1]     |\n| 3    | [2]     |\n\n#### Step 2: Perform Topological Sorting\n\nWe need to determine the order in which to place the numbers in the rows and columns using topological sorting.\n\n**Topological Sort for Rows:**\n\n| Node | Visited | DFS Path | Topological Order |\n|------|---------|----------|-------------------|\n| 1    | 0       | Start    |                   |\n| 1    | 2       | Visit 1  |                   |\n| 2    | 2       | Visit 2  |                   |\n| 2    | 1       | Backtrack|                   |\n| 1    | 1       | Backtrack| 2                 |\n| 3    | 0       | Start    |                   |\n| 3    | 2       | Visit 3  |                   |\n| 2    | 1       | Skip     |                   |\n| 3    | 1       | Backtrack| 3                 |\n|      |         |          | 1                 |\n\n**Final Row Topological Order:** `[3, 1, 2]`\n\n**Topological Sort for Columns:**\n\n| Node | Visited | DFS Path | Topological Order |\n|------|---------|----------|-------------------|\n| 2    | 0       | Start    |                   |\n| 2    | 2       | Visit 2  |                   |\n| 1    | 2       | Visit 1  |                   |\n| 1    | 1       | Backtrack|                   |\n| 2    | 1       | Backtrack| 1                 |\n| 3    | 0       | Start    |                   |\n| 3    | 2       | Visit 3  |                   |\n| 2    | 1       | Skip     |                   |\n| 3    | 1       | Backtrack| 2                 |\n|      |         |          | 3                 |\n\n**Final Column Topological Order:** `[3, 2, 1]`\n\n#### Step 3: Construct the Matrix\n\nUsing the topological orders, place each number in the corresponding position in the \\( k \\times k \\) matrix.\n\n**Row Indices:**\n\n| Number | Row Index |\n|--------|-----------|\n| 3      | 0         |\n| 1      | 1         |\n| 2      | 2         |\n\n**Column Indices:**\n\n| Number | Column Index |\n|--------|--------------|\n| 3      | 0            |\n| 2      | 1            |\n| 1      | 2            |\n\n**Matrix Construction:**\n\n- Place `3` at `(0, 0)`\n- Place `1` at `(1, 2)`\n- Place `2` at `(2, 1)`\n\n**Final Matrix:**\n\n|   | 0 | 1 | 2 |\n|---|---|---|---|\n| 0 | 3 | 0 | 0 |\n| 1 | 0 | 0 | 1 |\n| 2 | 0 | 2 | 0 |\n\n---\n\n# Code\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```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```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/3465aeb5-2380-423c-baed-c563794727e1_1721524265.4066358.png)\n
['Array', 'Graph', 'Topological Sort', 'Matrix', 'Python', 'C++', 'Java', 'JavaScript']