💯✅🔥Detailed Easy Java ,Python3 ,C++ Solution|| 10 ms ||≧◠‿◠≦✌
Intuition\nThe problem requires constructing a k x k matrix where each element must satisfy certain ordering constraints specified by rowConditions and colCondi
# Intuition\nThe problem requires constructing a `k x k` matrix where each element must satisfy certain ordering constraints specified by `rowConditions` and `colConditions`. The constraints dictate that if there is a condition like `[a, b]`, then `a` must appear before `b` in the respective row or column.\n\nTo solve this problem, we can leverage **topological sorting**, which is a method used to order the vertices of a directed graph such that for every directed edge `u -> v`, vertex `u` comes before vertex `v` in the ordering. This is particularly useful here since the row and column conditions can be represented as directed graphs.\n\n---\n# Approach\n1. **Graph Representation**: \n   - Each condition is treated as a directed edge in a graph. For example, if we have a condition `[a, b]`, it means there is a directed edge from `a` to `b`.\n   - We will maintain an adjacency list to represent the graph and an array to keep track of the in-degrees (number of incoming edges) for each node.\n\n2. **Topological Sorting**:\n   - We perform topological sorting twice: once for the row conditions and once for the column conditions.\n   - We use Kahn\'s algorithm for topological sorting, which involves:\n     - Initializing a queue with all nodes that have an in-degree of zero (these can be placed in the matrix first).\n     - Iteratively removing nodes from the queue, adding them to the sorted order, and decreasing the in-degree of their neighbors. If any neighbor\u2019s in-degree drops to zero, it is added to the queue.\n\n3. **Matrix Construction**:\n   - After obtaining the topological orders for both row and column conditions, we create the `k x k` matrix.\n   - We use a mapping from the column order to their respective indices to place elements in the correct positions according to the row order.\n\n4. **Edge Cases**:\n   - If the size of either topological order is less than `k`, it indicates that it is impossible to satisfy the conditions, and we return an empty matrix.\n\n---\n# Time Complexity\n- **Topological Sorting**: The time complexity for each topological sort is $$O(V + E)$$, where $$V$$ is the number of vertices (equal to `k`) and $$E$$ is the number of edges (equal to the number of conditions).\n  - In the worst case, if we assume that each condition is a unique edge, we can consider $$E$$ to be at most $$O(k^2)$$ (though typically it would be much less).\n- Therefore, the overall time complexity for both topological sorts is:\n  $$\n  O(k + E) + O(k + E) = O(k + E)\n  $$\n\n- **Matrix Construction**: This takes $$O(k)$$ time to fill in the matrix.\n\nThus, the overall time complexity is:\n$$\nO(k + E)\n$$\n\n---\n# Space Complexity\n- **Graph Representation**: The adjacency list and the in-degree array both require $$O(k + E)$$ space.\n- **Other Data Structures**: The queue used for Kahn\'s algorithm and the list for storing the topological order also require $$O(k)$$ space.\n\nTherefore, the overall space complexity is:\n$$\nO(k + E)\n$$\n\n---\n# Step By Step Explantion\n\nThe provided code implements a solution to build a matrix based on specified row and column conditions using topological sorting. Let\'s break down the code step by step, particularly focusing on the input values `k = 3`, `rowConditions = [[1,2],[2,3],[3,1],[2,3]]`, and `colConditions = [[2,1]]`.\n\n### Step 1: Input Initialization\n\n1. **Input Parameters**:\n   - `k = 3`: This indicates the size of the matrix we want to build, which will be a 3x3 matrix.\n   - `rowConditions = [[1,2],[2,3],[3,1],[2,3]]`: This specifies that:\n     - 1 must be before 2.\n     - 2 must be before 3.\n     - 3 must be before 1 (which creates a cycle).\n     - 2 must be before 3 (redundant).\n   - `colConditions = [[2,1]]`: This specifies that:\n     - 2 must be before 1 in the columns.\n\n### Step 2: Topological Sorting for Row Conditions\n\n2. **Calling `GenerateTopologicalSort` for Row Conditions**:\n   - The method is called with `rowConditions` and `k`.\n   - An adjacency list (`graph`) is created to represent the directed graph based on the conditions.\n   - The degree array (`deg`) is initialized to keep track of the number of incoming edges for each node.\n\n3. **Building the Graph**:\n   - For each condition in `rowConditions`, edges are added to the graph and the degree array is updated:\n     - From 1 to 2: `deg` becomes 1.\n     - From 2 to 3: `deg` becomes 1.\n     - From 3 to 1: `deg` becomes 1.\n     - From 2 to 3 (redundant).\n\n   The resulting graph and degree array will look like this:\n   - `graph = [, , , []]` (1 -> 2, 2 -> 3, 3 -> 1)\n   - `deg = [1, 1, 1]` (each node has one incoming edge).\n\n4. **Queue Initialization**:\n   - Nodes with zero incoming edges are added to the queue. Since all nodes have at least one incoming edge, the queue remains empty.\n\n5. **Topological Sort Completion**:\n   - Since the queue is empty, the topological sort cannot complete, and the method returns an empty list.\n\n### Step 3: Topological Sorting for Column Conditions\n\n6. **Calling `GenerateTopologicalSort` for Column Conditions**:\n   - Similar steps are followed for `colConditions`.\n   - The graph is initialized again, and the degree array is updated based on the column conditions.\n\n7. **Building the Graph for Columns**:\n   - From 2 to 1: `deg` becomes 1.\n   - The resulting graph for columns will be:\n   - `graph = [, []]` (2 -> 1)\n   - `deg = [1, 0]` (1 has one incoming edge, 2 has none).\n\n8. **Queue Initialization**:\n   - Node 2 (index 1) is added to the queue since it has zero incoming edges.\n\n9. **Topological Sort Completion for Columns**:\n   - The algorithm processes node 2, adds it to the order, and then processes node 1, resulting in the order: `[2, 1]`.\n\n### Step 4: Validating the Results\n\n10. **Checking Topological Sort Results**:\n    - The result from the row conditions is empty, indicating that a cycle was detected.\n    - The result from the column conditions is `[2, 1]`, which is valid.\n\n11. **Final Validation**:\n    - Since the row order is empty (indicating that the matrix cannot be constructed due to the cycle), the method returns an empty matrix `new int`.\n\n### Conclusion\n\nThe final output of the `buildMatrix` function, given the input parameters, is an empty matrix because the row conditions create a cycle that prevents a valid topological sort. The code effectively detects this condition and handles it gracefully by returning an empty result. \n\nThis step-by-step explanation illustrates how the topological sorting process works and how it is applied to the given conditions to determine the feasibility of constructing the desired matrix.\n\n---\n\n```java []\nclass Solution {\n    public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {\n        List<Integer> order1 = GenerateTopologicalSort(rowConditions, k);\n        List<Integer> order2 = GenerateTopologicalSort(colConditions, k);\n        if (order1.size() < k || order2.size() < k)\n            return new int[0][0];\n        Map<Integer, Integer> m = new HashMap();\n        for (int i = 0; i < k; i++)\n            m.put(order2.get(i), i);\n        int[][] ans = new int[k][k];\n        for (int i = 0; i < k; i++)\n            ans[i][m.get(order1.get(i))] = order1.get(i);\n        return ans;\n    }\n\n    private List<Integer> GenerateTopologicalSort(int[][] A, int k) {\n        int[] deg = new int[k];\n        List<Integer> order = new ArrayList();\n        List<List<Integer>> graph = new ArrayList();\n        for (int i = 0; i < k; i++)\n            graph.add(new ArrayList());\n        Queue<Integer> q = new LinkedList();\n        for (int[] c : A) {\n            graph.get(c[0] - 1).add(c[1] - 1);\n            deg[c[1] - 1]++;\n        }\n        for (int i = 0; i < k; i++)\n            if (deg[i] == 0)\n                q.add(i);\n        while (!q.isEmpty()) {\n            int x = q.poll();\n            order.add(x + 1);\n            for (int y : graph.get(x))\n                if (--deg[y] == 0)\n                    q.add(y);\n        }\n        return order;\n    }\n}\n```\n```python3 []\nclass Solution:\n    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n        order1 = self.generate_topological_sort(rowConditions, k)\n        order2 = self.generate_topological_sort(colConditions, k)\n        \n        if len(order1) < k or len(order2) < k:\n            return []\n        \n        m = {order2[i]: i for i in range(k)}\n        ans = [[0] * k for _ in range(k)]\n        \n        for i in range(k):\n            ans[i][m[order1[i]]] = order1[i]\n        \n        return ans\n\n    def generate_topological_sort(self, A: List[List[int]], k: int) -> List[int]:\n        deg = [0] * k\n        order = []\n        graph = defaultdict(list)\n        q = deque()\n        \n        for c in A:\n            graph[c[0] - 1].append(c[1] - 1)\n            deg[c[1] - 1] += 1\n        \n        for i in range(k):\n            if deg[i] == 0:\n                q.append(i)\n        \n        while q:\n            x = q.popleft()\n            order.append(x + 1)\n            for y in graph[x]:\n                deg[y] -= 1\n                if deg[y] == 0:\n                    q.append(y)\n        \n        return order\n```\n```C++ []\nclass Solution {\npublic:\n    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {\n        vector<int> order1 = generateTopologicalSort(rowConditions, k);\n        vector<int> order2 = generateTopologicalSort(colConditions, k);\n        \n        if (order1.size() < k || order2.size() < k) {\n            return {};\n        }\n        \n        unordered_map<int, int> m;\n        for (int i = 0; i < k; i++) {\n            m[order2[i]] = i;\n        }\n        \n        vector<vector<int>> ans(k, vector<int>(k, 0));\n        for (int i = 0; i < k; i++) {\n            ans[i][m[order1[i]]] = order1[i];\n        }\n        \n        return ans;\n    }\n\nprivate:\n    vector<int> generateTopologicalSort(const vector<vector<int>>& A, int k) {\n        vector<int> deg(k, 0);\n        vector<int> order;\n        vector<vector<int>> graph(k);\n        queue<int> q;\n        \n        for (const auto& c : A) {\n            graph[c[0] - 1].push_back(c[1] - 1);\n            deg[c[1] - 1]++;\n        }\n        \n        for (int i = 0; i < k; i++) {\n            if (deg[i] == 0) {\n                q.push(i);\n            }\n        }\n        \n        while (!q.empty()) {\n            int x = q.front();\n            q.pop();\n            order.push_back(x + 1);\n            for (int y : graph[x]) {\n                if (--deg[y] == 0) {\n                    q.push(y);\n                }\n            }\n        }\n        \n        return order;\n    }\n};\n```\n---\n\n\n\n---\n![upvote.png](https://assets.leetcode.com/users/images/dfa693d1-5e12-420d-887a-e2808476fad9_1721532356.9333653.png)\n\n---
['Array', 'Graph', 'Topological Sort', 'Matrix', 'C++', 'Java', 'Python3']