🔥🔥 ✅ Beats 100 %solutions with Detailed explanation || C++ || JAVA || Python
Intuition Behind the Solution\n\nThe problem involves building a \( k \times k \) matrix with specific conditions on the ordering of rows and columns. The core 
# Intuition Behind the Solution\n\nThe problem involves building a \\( k \\times k \\) matrix with specific conditions on the ordering of rows and columns. The core idea is to use topological sorting to determine a valid order of elements based on the given conditions.\n\nHere\u2019s a step-by-step breakdown of the intuition:\n\n1. **Understand the Problem Constraints**:\n   - We need to place numbers \\( 1 \\) to \\( k \\) in a \\( k \\times k \\) matrix.\n   - Each number should appear exactly once.\n   - The matrix should satisfy both row and column conditions given in `rowConditions` and `colConditions`.\n\n2. **Graph Representation**:\n   - We can represent the row conditions as a directed graph where each edge \\( (a, b) \\) means \\( a \\) must appear in a row above \\( b \\).\n   - Similarly, we can represent the column conditions as another directed graph where each edge \\( (a, b) \\) means \\( a \\) must appear in a column to the left of \\( b \\).\n\n3. **Topological Sorting**:\n   - Topological sorting of a directed graph gives a linear ordering of its vertices such that for every directed edge \\( (u, v) \\), vertex \\( u \\) comes before \\( v \\) in the ordering.\n   - We perform topological sorting on the row graph to determine the row order of the elements.\n   - Similarly, we perform topological sorting on the column graph to determine the column order of the elements.\n\n4. **Building the Matrix**:\n   - Once we have the topological orders for rows and columns, we can place each element in the matrix according to these orders.\n   - We create a mapping from each element to its row and column indices based on the topological sort results.\n\n5. **Check for Cycles**:\n   - If there is a cycle in any of the graphs, a valid topological sort is not possible, which means the given conditions are contradictory, and we should return an empty matrix.\n\n\n# Approach and code breakdown\n\n##### Class Definition and Method Signature\n\n```java\nclass Solution {\n    public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {\n```\n\nThis is the main method of the `Solution` class. It takes two parameters:\n- `k`: The number of elements to place in the matrix.\n- `rowConditions`: An array of conditions that specify the order of elements in the rows.\n- `colConditions`: An array of conditions that specify the order of elements in the columns.\n\n### Initialize Graphs\n\n```java\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\n- **rowGraph** and **colGraph**: These are adjacency lists representing the directed graphs for row and column conditions, respectively. The graphs are initialized to have `k + 1` vertices (1-based index).\n- The loops populate the adjacency lists based on the given conditions.\n\n### Topological Sorting for Rows\n\n```java\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        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\n- `visited`: Array to keep track of the visitation state of each node (0 = unvisited, 1 = visited, 2 = visiting).\n- `queue`: Used to store the topological order.\n- **Topological Sort**: The `topSort` method is called for each node to generate a topological order of the row conditions.\n- `rowIndexMap`: Maps each node to its position in the topological order for rows.\n\n### Topological Sorting for Columns\n\n```java\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\n- Resets `visited` and `queue` for the column conditions.\n- **Topological Sort**: Similar process as rows but for column conditions.\n- `colOrder` and `colIndexMap`: Store the topological order for columns and map each node to its position in the topological order.\n\n### Build the Result Matrix\n\n```java\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- `result`: The final `k x k` matrix.\n- Places each number `i` at the correct position based on `rowIndexMap` and `colIndexMap`.\n\n### Topological Sort Helper Method\n\n```java\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\n- **topSort**: Recursive method to perform topological sorting.\n- If a cycle is detected (`visited[node] == 2`), it returns false.\n- Marks the node as visiting (`visited[node] = 2`) and recursively visits all its children.\n- Once all children are visited, marks the node as visited (`visited[node] = 1`) and adds it to the queue.\n\nThis code ensures that the rows and columns of the matrix adhere to the given conditions by performing a topological sort and placing the elements accordingly.\n\n```C++ []\nclass Solution {\npublic:\n    std::vector<std::vector<int>> buildMatrix(int k, std::vector<std::vector<int>>& rowConditions, std::vector<std::vector<int>>& colConditions) {\n        std::vector<std::vector<int>> rowGraph(k + 1);\n        for (const auto& rowCondition : rowConditions) {\n            rowGraph[rowCondition[0]].push_back(rowCondition[1]);\n        }\n\n        std::vector<std::vector<int>> colGraph(k + 1);\n        for (const auto& colCondition : colConditions) {\n            colGraph[colCondition[0]].push_back(colCondition[1]);\n        }\n\n        std::vector<int> visited(k + 1, 0);\n        std::deque<int> queue;\n        for (int i = 1; i <= k; ++i) {\n            if (!topSort(rowGraph, i, visited, queue)) {\n                return {};\n            }\n        }\n\n        std::vector<int> rowIndexMap(k + 1);\n        for (int i = 0; i < k; ++i) {\n            int node = queue.back(); queue.pop_back();\n            rowIndexMap[node] = i;\n        }\n\n        visited.assign(k + 1, 0);\n        queue.clear();\n        for (int i = 1; i <= k; ++i) {\n            if (!topSort(colGraph, i, visited, queue)) {\n                return {};\n            }\n        }\n\n        std::vector<int> colOrder(k);\n        std::vector<int> colIndexMap(k + 1);\n        for (int i = 0; i < k; ++i) {\n            int node = queue.back(); queue.pop_back();\n            colOrder[i] = node;\n            colIndexMap[node] = i;\n        }\n\n        std::vector<std::vector<int>> result(k, std::vector<int>(k, 0));\n        for (int i = 1; i <= k; ++i) {\n            result[rowIndexMap[i]][colIndexMap[i]] = i;\n        }\n\n        return result;\n    }\n\nprivate:\n    bool topSort(const std::vector<std::vector<int>>& graph, int node, std::vector<int>& visited, std::deque<int>& queue) {\n        if (visited[node] == 2) return false;\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.push_back(node);\n        }\n        return true;\n    }\n};\n\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```python []\nclass Solution:\n    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n        rowGraph = defaultdict(list)\n        for a, b in rowConditions:\n            rowGraph[a].append(b)\n        \n        colGraph = defaultdict(list)\n        for a, b in colConditions:\n            colGraph[a].append(b)\n        \n        def topSort(graph):\n            visited = [0] * (k + 1)\n            stack = deque()\n            \n            def dfs(node):\n                if visited[node] == 2:\n                    return False\n                if visited[node] == 0:\n                    visited[node] = 2\n                    for child in graph[node]:\n                        if not dfs(child):\n                            return False\n                    visited[node] = 1\n                    stack.appendleft(node)\n                return True\n            \n            for i in range(1, k + 1):\n                if not dfs(i):\n                    return []\n            return stack\n        \n        rowOrder = topSort(rowGraph)\n        if not rowOrder:\n            return []\n        \n        colOrder = topSort(colGraph)\n        if not colOrder:\n            return []\n        \n        rowIndex = {num: i for i, num in enumerate(rowOrder)}\n        colIndex = {num: i for i, num in enumerate(colOrder)}\n        \n        result = [[0] * k for _ in range(k)]\n        for num in range(1, k + 1):\n            result[rowIndex[num]][colIndex[num]] = num\n        \n        return result\n\n```\n![UP.png](https://assets.leetcode.com/users/images/703c3ac9-d232-4faa-9306-150f362f7d66_1721538146.159382.png)\n
['Array', 'Graph', 'Topological Sort', 'Matrix', 'C++', 'Java']