Topological Sort Approach to Build Matrix from Row and Column Conditions || 💯💯💯
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem requires creating a matrix based on row and column conditions, which repres
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires creating a matrix based on row and column conditions, which represent dependencies. Topological sorting is well-suited for this kind of dependency management, as it helps us find a valid ordering for the elements.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Topological Sorting**: Use Kahn\'s Algorithm (BFS) to find the topological order for both row and column conditions.\n2. **Build Matrix**: Once we have the topological order for rows and columns, use these orders to place the numbers in the matrix.\n\n# Complexity\n- Time complexity: $$O(V+E)$$ where V is the number of vertices and E is the number of edges. This is due to the topological sorting for both row and column conditions.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(V+E)$$ for the adjacency list, queue, and other auxiliary space used.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public int[] topoSort(int V, int pairs[][]) {\n        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();\n\n        for(int i=0; i<=V; i++){\n            adj.add(new ArrayList<>());\n        }\n        for(int pair[] : pairs){\n            int u = pair[0];\n            int v = pair[1];\n            adj.get(u).add(v);\n        }\n        int indegree[] = new int[V+1];\n        for(int u=0; u<adj.size(); u++){\n            for(int v: adj.get(u)){\n                indegree[v]++;\n            }\n        }\n\n        Queue<Integer> queue = new LinkedList<>();\n        for(int i=1; i<=V; i++){\n            if(indegree[i] == 0){\n                queue.offer(i);\n            }\n        }\n        ArrayList<Integer> res = new ArrayList<>();\n        while(!queue.isEmpty()){\n            int node = queue.poll();\n            res.add(node);\n            for(int neighbour : adj.get(node)){\n                indegree[neighbour]--;\n                if(indegree[neighbour]==0){\n                    queue.offer(neighbour);\n                }\n            }\n        }\n\n        if(res.size() != V){\n            return new int[0];\n        }\n\n        int ans[] = new int[V];\n        for(int i=0; i<V; i++){\n            ans[i] = res.get(i);\n        }\n        return ans;\n    }\n    public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {\n        int rowToposort[] = topoSort(k, rowConditions);\n        if(rowToposort.length == 0){\n            return new int[0][0];\n        }\n        int colToposort[] = topoSort(k, colConditions);\n        if(colToposort.length == 0){\n            return new int[0][0];\n        }\n        int matrix[][] = new int[k][k];\n        for(int i=0; i<k; i++){\n            for(int j=0; j<k; j++){\n                if(rowToposort[i] == colToposort[j]){\n                    matrix[i][j] = colToposort[j];\n                }\n            }\n        }\n        return matrix;\n    }\n}\n```
['Java']