Simply Explained ✨
Intuition\nTo solve this problem, we need to find a valid way to place each number from 1 to k in a k x k matrix such that all given row and column conditions a
# Intuition\nTo solve this problem, we need to find a valid way to place each number from 1 to k in a k x k matrix such that all given row and column conditions are satisfied. This can be done using topological sorting. We first create the topological order for rows and columns separately using the given conditions and then place the numbers in the matrix accordingly.\n\n# Approach\n1. **Graph Construction**:\n   - Construct two graphs, one for row conditions and one for column conditions, using the given `rowConditions` and `colConditions` arrays.\n   - Each node represents a number from 1 to k, and directed edges represent the conditions.\n\n2. **Topological Sort**:\n   - Perform topological sorting on both graphs to determine the order of placement for rows and columns.\n   - If a cycle is detected during topological sorting, return an empty matrix since it is impossible to satisfy the conditions.\n\n3. **Matrix Construction**:\n   - Using the topological orders obtained for rows and columns, place each number in the matrix at the position determined by its order.\n\n# Complexity\n- Time complexity: \\(O(k^2)\\), where \\(k\\) is the given integer, due to graph construction and topological sorting.\n- Space complexity: \\(O(k^2)\\) for storing the graphs and matrix.\n\n# Code\n```\nimport java.util.*;\n\nclass Solution {\n    public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {\n        // Get the topological order for rows and columns\n        int[] rowOrder = topologicalSort(k, rowConditions);\n        int[] colOrder = topologicalSort(k, colConditions);\n\n        // If any order is null, it means there\'s a cycle and we can\'t construct the matrix\n        if (rowOrder == null || colOrder == null) {\n            return new int[0][0];\n        }\n\n        // Initialize the result matrix\n        int[][] matrix = new int[k][k];\n        \n        // Create position arrays to store the position of each number in the row and column order\n        int[] rowPos = new int[k + 1];\n        int[] colPos = new int[k + 1];\n\n        // Fill position arrays with the index positions from the topological order\n        for (int i = 0; i < k; i++) {\n            rowPos[rowOrder[i]] = i;\n            colPos[colOrder[i]] = i;\n        }\n\n        // Place each number in the matrix according to the topological order positions\n        for (int i = 1; i <= k; i++) {\n            matrix[rowPos[i]][colPos[i]] = i;\n        }\n\n        return matrix;\n    }\n\n    private int[] topologicalSort(int k, int[][] conditions) {\n        // Create an adjacency list for the graph\n        List<Integer>[] graph = new ArrayList[k + 1];\n        // Initialize indegree array to count the number of incoming edges for each node\n        int[] indegree = new int[k + 1];\n\n        // Initialize the adjacency list\n        for (int i = 0; i <= k; i++) {\n            graph[i] = new ArrayList<>();\n        }\n\n        // Build the graph from the conditions\n        for (int[] condition : conditions) {\n            int u = condition[0];\n            int v = condition[1];\n            graph[u].add(v);\n            indegree[v]++;\n        }\n\n        // Initialize a queue to perform topological sorting\n        Queue<Integer> queue = new LinkedList<>();\n        // Add all nodes with no incoming edges to the queue\n        for (int i = 1; i <= k; i++) {\n            if (indegree[i] == 0) {\n                queue.add(i);\n            }\n        }\n\n        // Array to store the topological order\n        int[] order = new int[k];\n        int index = 0;\n\n        // Perform BFS to get the topological order\n        while (!queue.isEmpty()) {\n            int node = queue.poll();\n            order[index++] = node;\n\n            // Reduce the indegree of the neighbors and add them to the queue if their indegree becomes 0\n            for (int neighbor : graph[node]) {\n                if (--indegree[neighbor] == 0) {\n                    queue.add(neighbor);\n                }\n            }\n        }\n\n        // If we have processed all nodes, return the order; otherwise, return null (indicating a cycle)\n        return index == k ? order : null;\n    }\n}\n\n```
['Java']