C# Solution for Build a Matrix With Conditions Problem
Intuition\n Describe your first thoughts on how to solve this problem. \nThe approach involves:\n\n\t1.\tTopological Sorting: Using Kahn\u2019s algorithm to fin
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe approach involves:\n\n\t1.\tTopological Sorting: Using Kahn\u2019s algorithm to find the order of elements based on the given constraints.\n\t2.\tMatrix Construction: Filling in the matrix based on the sorted row and column orders.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe solution is based on the concept of topological sorting and matrix construction:\n\n1.\tTopological Sorting:\n\t\u2022\tIntuition: Topological sorting is used to order vertices of a directed graph in such a way that for every directed edge  uv  from vertex  u  to vertex  v ,  u  comes before  v  in the ordering. This is particularly useful for resolving constraints that define ordering (like \u201Cnumber  A  must be above number  B \u201D).\n\t\u2022\tApproach:\n\t    \u2022\tGraph Construction: Build adjacency lists from constraints for rows and columns separately.\n\t    \u2022\tIn-Degree Array: Track how many incoming edges each node has.\n\t    \u2022\tKahn\u2019s Algorithm: Use a queue to process nodes with zero in-degrees and keep track of nodes whose ordering is resolved. Remove edges as you process nodes and update in-degrees of neighbors. If any nodes remain with non-zero in-degrees at the end, a cycle exists, making a valid ordering impossible.\n2.\tMatrix Construction:\n\t\u2022\tIntuition: Once we have the topological order for rows and columns, the next step is to place numbers into the matrix such that the order constraints are respected.\n\t\u2022\tApproach:\n\t    \u2022\tMatrix Initialization: Create a  k x k  matrix initialized with zeros.\n\t    \u2022\tPlacement: For each number, place it in the matrix based on its position in the topological order of rows and columns. The position in the row order determines the row, and the position in the column order determines the column.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\u2022\tGraph Construction:  O(E) , where  E  is the number of edges (constraints). This involves processing each edge once to build the adjacency list and update in-degrees.\n\u2022\tTopological Sorting:  O(V + E) , where  V  is the number of vertices (numbers) and  E  is the number of edges. The time complexity for Kahn\u2019s algorithm is linear in terms of the number of vertices plus the number of edges.\n\u2022\tMatrix Filling:  O(k^2) , where  k  is the matrix size. This involves iterating over the matrix to place numbers based on the sorted orders.\nOverall Time Complexity:  O(k^2 + E) , since the matrix filling dominates for large  k  compared to the edge operations.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\u2022\tGraph Representation:  O(V + E)  for storing adjacency lists and in-degrees.\n\u2022\tTopological Sorting Storage:  O(V)  for the sorted order and queue.\n\u2022\tMatrix Storage:  O(k^2)  for the matrix.\nOverall Space Complexity:  O(k^2 + k + E) , which simplifies to  O(k^2 + E)  since  k^2  will dominate for large  k .\n\n# Code\n```\nusing System;\nusing System.Collections.Generic;\n\npublic class Solution {\n    public int[][] BuildMatrix(int k, int[][] rowConditions, int[][] colConditions) {\n        int[] rowOrder = TopoSort(rowConditions, k);\n        int[] colOrder = TopoSort(colConditions, k);\n        \n        if (rowOrder.Length == 0 || colOrder.Length == 0) {\n            return new int[0][];\n        }\n        \n        int[][] matrix = new int[k][];\n        for (int i = 0; i < k; i++) {\n            matrix[i] = new int[k];\n        }\n        \n        // Fill the matrix based on the orders\n        for (int i = 0; i < k; i++) {\n            int rowPos = Array.IndexOf(rowOrder, i + 1);\n            int colPos = Array.IndexOf(colOrder, i + 1);\n            \n            if (rowPos >= 0 && rowPos < k && colPos >= 0 && colPos < k) {\n                matrix[rowPos][colPos] = i + 1;\n            }\n        }\n        \n        return matrix;\n    }\n    \n    private int[] TopoSort(int[][] edges, int n) {\n        List<int>[] adj = new List<int>[n + 1];\n        for (int i = 0; i <= n; i++) {\n            adj[i] = new List<int>();\n        }\n        \n        int[] inDegree = new int[n + 1];\n        foreach (var edge in edges) {\n            int u = edge[0];\n            int v = edge[1];\n            adj[u].Add(v);\n            inDegree[v]++;\n        }\n        \n        Queue<int> queue = new Queue<int>();\n        for (int i = 1; i <= n; i++) {\n            if (inDegree[i] == 0) {\n                queue.Enqueue(i);\n            }\n        }\n        \n        List<int> result = new List<int>();\n        while (queue.Count > 0) {\n            int node = queue.Dequeue();\n            result.Add(node);\n            foreach (int neighbor in adj[node]) {\n                if (--inDegree[neighbor] == 0) {\n                    queue.Enqueue(neighbor);\n                }\n            }\n        }\n        \n        if (result.Count != n) {\n            return new int[0]; // Cycle detected or not all nodes are reachable\n        }\n        \n        return result.ToArray();\n    }\n}\n```
['C#']