Topological Sort & cycle detection using DFS | JAVA | 18ms | 100%
\nclass Solution {\n    public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {\n        \n        int[][] ans = new int[k][k];\n     
```\nclass Solution {\n    public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {\n        \n        int[][] ans = new int[k][k];\n        \n        // create adjacency List for the rows and columns\n        Map<Integer, Set<Integer>> adjListRow = new HashMap<>();\n        Map<Integer, Set<Integer>> adjListCol = new HashMap<>();\n        for(int[] row : rowConditions){\n            adjListRow.putIfAbsent(row[0], new HashSet<>());\n            adjListRow.get(row[0]).add(row[1]);\n        }\n        for(int[] col : colConditions){\n            adjListCol.putIfAbsent(col[0], new HashSet<>());\n            adjListCol.get(col[0]).add(col[1]);\n        }\n        \n        // run DFS with cycle detection while storing the finish order of the nodes\n        Map<Integer, Integer> rowIndex = new HashMap<>();\n        Map<Integer, Integer> colIndex = new HashMap<>();\n        int[] visitedRow = new int[k+1];\n        int[] visitedCol = new int[k+1];\n        for(int i = 1; i <= k; i++){\n            if(!(dfs(i, adjListRow, visitedRow, rowIndex) && dfs(i, adjListCol, visitedCol, colIndex)))\n               return new int[0][0];\n        }\n       \n\t   // assign the correct position to the nodes according to the finish order\n        for( int i = 1; i <= k; i++){\n            int r = rowIndex.size() - rowIndex.get(i) - 1;\n            int c = colIndex.size() - colIndex.get(i) - 1;\n            ans[r][c] = i;\n        }\n        \n        return ans;\n    }\n    \n\t/** DFS with cycle detection (returns false in case of a cycle) \n\tState of a node can be one of the following\n\t\t0 -> unvisited\n\t\t1 -> visiting\n\t\t2 -> visited\n    On the DFS path visiting a node with value 1 means we are visiting a node on the path we came from -> hence it is a cycle(DFS returns false). When a visited node is encountered, we can return back to the caller node.\n\t*/\n    private boolean dfs(int node, Map<Integer, Set<Integer>> adjList, int[] visited, Map<Integer, Integer>  map){\n\t \n        if(visited[node] == 2) return true;\n        if(visited[node] == 1) return false;\n        visited[node] = 1;\n\t\t\n        Set<Integer> list = adjList.get(node);\n        if(list != null)\n            for(int ele : list)\n                if(visited[ele] != 2)\n                    if(!dfs(ele, adjList, visited, map)) return false;\n                \n\t\t// mark the node visited and add to the map of finished nodes with the finish number\n        visited[node] = 2;\n        map.put(node, map.size());\n        return true;\n    } \n}\n```
['Depth-First Search', 'Topological Sort', 'Java']