Easy Explanation + Code with comments | Doubt of building matrix at end | Java | BFS | TopSort
From diffferent you might already know it is topological sort. But there is no harm in revising it.\nApproach:\nIn question, condition is given that a number sh
From diffferent you might already know it is topological sort. But there is no harm in revising it.\nApproach:\nIn question, condition is given that a number should occur before other number in row/column and such conditions are many. This is cue for topological sort.\n\nNow, imagine we dont have to create 2D matrix at the end and simply a 1D matrix need to be form. Then only one array of conditions would be given in the question and we form a graph and perform topological sort.\n**Example 1:** if given: k = 3, rowConditions = [[1,2],[3,2]]\nthen this graph will be formed :\n1 ---> 2 <--- 3\nand its topological sorted array would be : 1, 3, 2 (we will use this further in explaination) or 3, 2, 1.\nIn this we know position of 1 is at 0 index, position of 3 is at 1 index, position of 2 will be at 2 index.\n\nTill now all good.\n\nNow, if above is given for column then also, can perform similar.\n**Example 2:** given inputs are : k = 3, colConditions = [[2,1],[3,2]]\nGraph will be:\n3 ---> 2 ---> 1\nTopological sort will be 3, 2, 1\nAlso, we know position of 3 is at 0 index, position of 2 is at 1 index, position of 1 will be at 2 index.\n\nNow comes the real question, **How to build matrix ?** \nSimply assume the positions in Example 1 are row numbers, means in which row these need to be inserted or we are forming a 1D array in vertical form like:\n![image](https://assets.leetcode.com/users/images/f732d735-2f5e-44f3-bb4d-1e976c6f6e00_1662136945.8450797.jpeg)\n\nFor Example 2 assume, positions are columns number and our 1D array will be in horizontal form like:\n![image](https://assets.leetcode.com/users/images/f8aa9df7-c81b-476f-b40c-83a4e1c37da6_1662137146.3878105.jpeg)\n\nNow for each number we know its row index and its column index, so we can create the matrix using that:\nPsuedoCode:\n```\nfor(int i = 1; i <=k ; i++){\n\tmatrix[position of i in row][position of i in column] = i\n}\n```\n```\nclass Solution {\n    public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {\n        Map<Integer, Set<Integer>> rowGraph = new HashMap<>();\n        Map<Integer, Set<Integer>> colGraph = new HashMap<>();\n        int[] inDegreeRow = new int[k+1];\n        int[] inDegreeCol = new int[k+1];\n\n        // Initalizing the map so that we dont have to check for null\n        for(int i = 0; i <= k; i++) {\n            rowGraph.put(i, new HashSet<>());\n            colGraph.put(i, new HashSet<>());\n        }\n\n        // building a graph for row conditions along with populating the inDegree of each node.\n        buildGraph(rowConditions, inDegreeRow, rowGraph);\n        // building a graph for column conditions along with populating the inDegree of each node.\n        buildGraph(colConditions, inDegreeCol, colGraph);\n\n        // Finding Topological sort\n        // or mapping of node/numbers to its position where it should be in row (index). \n        Map<Integer, Integer> rowTopoSort = getTopologicalSort(rowGraph, inDegreeRow, k);\n        \n        // Finding Topological sort\n        // or mapping of node/numbers to its position where it should be in column (index). \n        Map<Integer, Integer> colTopoSort = getTopologicalSort(colGraph, inDegreeCol, k);\n\n        // If we are not able to cover all nodes/numbers means there is cycle.\n        if(rowTopoSort.size() != k || colTopoSort.size() != k) return new int[0][0];\n\n        // Building tha metric usinbg the mapping we get from topological sort.\n        return buildMatrix(k, rowTopoSort, colTopoSort);\n    }\n\n    private void buildGraph(int[][] conditions, int[] inDegree, Map<Integer, Set<Integer>> graph){\n        for (int[] condition : conditions){\n            int u = condition[0];\n            int v = condition[1];\n\n            Set<Integer> s = graph.get(u);\n            s.add(v);\n            graph.put(u, s);\n        }\n\n        for(int i = 1; i < inDegree.length; i++){\n            for(int neighbour : graph.get(i)){\n                inDegree[neighbour]++;\n            }\n        }\n    }\n\n    private Map<Integer, Integer> getTopologicalSort(Map<Integer, Set<Integer>> graph, int[] inDegree, int k){\n        Map<Integer, Integer> numToPoistionMap = new HashMap<>();\n        Queue<Integer> queue = new LinkedList<>();\n        for(int i = 1; i <= k; i++){\n            if(inDegree[i] == 0) queue.offer(i);\n        }\n\n        int position = 0;\n        while(!queue.isEmpty()){\n            int head = queue.poll();\n            numToPoistionMap.put(head, position++);\n\n            for(int neighbour : graph.get(head)){\n                inDegree[neighbour]--;\n\n                if(inDegree[neighbour] == 0) queue.offer(neighbour);\n            }\n        }\n\n        return numToPoistionMap;\n    }\n\n    private int[][] buildMatrix(int k, Map<Integer, Integer> rowMap, Map<Integer, Integer> colMap){\n        int[][] matrix = new int[k][k];\n\n        for(int i = 1 ; i <= k; i++){\n            matrix[rowMap.get(i)][colMap.get(i)] = i;\n        }\n\n        return matrix;\n    }\n}\n```\n\nThanks for reading. If you like please upvote.
['Breadth-First Search', 'Topological Sort', 'Java']