2392. SIMPLE STEP BY STEP SOLUTION
Intuition\nThe problem involves constructing a matrix with specific conditions on the rows and columns. The key idea is to use topological sorting to determine 
# Intuition\nThe problem involves constructing a matrix with specific conditions on the rows and columns. The key idea is to use topological sorting to determine the order of elements based on the given conditions. If the conditions form a valid topological order, we can place the elements accordingly; otherwise, it\'s impossible to construct such a matrix.\n\n# Approach\n1. **Topological Sort**: Perform topological sorting on the `rowConditions` and `colConditions` to determine the order of elements for rows and columns.\n2. **Matrix Construction**: Using the obtained orders from the topological sorts, place the elements in their respective positions in the matrix.\n\n### Detailed Steps:\n1. **Topological Sort Function**:\n    - Compute in-degrees of all vertices.\n    - Build the graph from the given edge list.\n    - Use a queue to process vertices with zero in-degree and build the topological order.\n    - If all vertices are processed, return the topological order; otherwise, return an invalid result.\n\n2. **Main Function (`buildMatrix`)**:\n    - Get the row and column orders using the topological sort function.\n    - If either order is invalid, return an empty matrix.\n    - Construct the result matrix using the obtained orders by mapping the positions.\n\n## Dry Run\n\n### Test Case:\n**Input**: `k = 3`, `rowConditions = [[1, 2], [3, 2]]`, `colConditions = [[2, 1], [3, 2]]`\n**Output**: `[[3, 0, 0], [0, 0, 1], [0, 2, 0]]`\n\n### Step-by-Step Execution:\n1. **Topological Sort for Rows**:\n    - **Graph Construction**:\n        ```\n        graph = [[1], [], [1]]\n        inDegree = [0, 2, 0]\n        ```\n    - **Queue Initialization**: `queue = [0, 2]`\n    - **Processing**:\n        - Pop `0`: `topOrder = [0]`, `queue = [2]`, decrease in-degree of `1`.\n        - Pop `2`: `topOrder = [0, 2]`, `queue = [1]`, decrease in-degree of `1`.\n        - Pop `1`: `topOrder = [0, 2, 1]`\n    - **Row Order**: `[0, 2, 1]`\n\n2. **Topological Sort for Columns**:\n    - **Graph Construction**:\n        ```\n        graph = [[], [0], [1]]\n        inDegree = [1, 1, 0]\n        ```\n    - **Queue Initialization**: `queue = [2]`\n    - **Processing**:\n        - Pop `2`: `topOrder = [2]`, `queue = [1]`, decrease in-degree of `1`.\n        - Pop `1`: `topOrder = [2, 1]`, `queue = [0]`, decrease in-degree of `0`.\n        - Pop `0`: `topOrder = [2, 1, 0]`\n    - **Column Order**: `[2, 1, 0]`\n\n3. **Matrix Construction**:\n    - **Row Positions**: `[0, 2, 1]`\n    - **Column Positions**: `[2, 1, 0]`\n    - **Placing Elements**:\n        - Place `1` at `(0, 2)`\n        - Place `2` at `(2, 1)`\n        - Place `3` at `(1, 0)`\n    - **Result Matrix**:\n        ```\n        [[3, 0, 1],\n         [0, 0, 0],\n         [0, 2, 0]]\n        ```\n\n**Final Output**: `[[3, 0, 0], [0, 0, 1], [0, 2, 0]]`\n\n# Complexity\n- Time complexity:\n $$O(K^2)$$ \n\n- Space complexity:\n $$O(K^2)$$ \n\n# Code\n```\nclass Solution {\n    public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {\n\n        int[] rowOrder = topologicalSort(k, rowConditions);\n        int[] columnOrder = topologicalSort(k, colConditions);\n\n        if (rowOrder[0]== -1 || columnOrder[0] == -1) return new int[0][0];\n\n        int[][] resMatrix = new int[k][k];\n\n        int[] rowPosition = new int[k];\n        int[] colPosition = new int[k];\n\n        for (int i = 0; i < k; i++) {\n            rowPosition[rowOrder[i]] = i;\n            colPosition[columnOrder[i]] = i;\n        }\n\n        for (int i = 0; i < k; i++) {\n            resMatrix[rowPosition[i]][colPosition[i]] = i + 1;\n        }\n\n        return resMatrix;\n    }\n\n    public static int[] topologicalSort(int numVertices, int[][] conditionArray) {\n        int[] inDegree = new int[numVertices];\n        List<Integer>[] graph = new List[numVertices];\n\n        for (int i = 0; i < numVertices; i++) {\n            graph[i] = new ArrayList<>();\n        }\n\n        for (int[] edge : conditionArray) {\n            int u = edge[0] - 1;\n            int v = edge[1] - 1;\n            graph[u].add(v);\n            inDegree[v]++;\n        }\n\n        Queue<Integer> queue = new LinkedList<>();\n        for (int i = 0; i < numVertices; i++) {\n            if (inDegree[i] == 0) {\n                queue.add(i);\n            }\n        }\n\n        int[] topOrder = new int[numVertices];\n        int index = 0;\n\n        while (!queue.isEmpty()) {\n            int u = queue.poll();\n            topOrder[index++] = u;\n\n            for (int v : graph[u]) {\n                inDegree[v]--;\n                if (inDegree[v] == 0) {\n                    queue.add(v);\n                }\n            }\n        }\n\n        if (index != numVertices) {\n            int[] result = {-1} ;\n            return result ;\n        }\n        return topOrder;\n    }\n}\n```\n![image.png](https://assets.leetcode.com/users/images/b193bd88-4f0d-41f1-ad53-ca72d8a4cc9f_1721584440.9539273.png)\n
['Java']