Java | Topological Sort | No Cycle -> No Conflict
Model\nWe can model this as a directed graph, with above -> below and left -> right.\nWe will need to verify that there is no cycle and find out where its suppo
#### Model\nWe can model this as a directed graph, with `above -> below` and `left -> right`.\nWe will need to verify that there is no cycle and find out where its supposed `row` and `col` position is.\n\n#### Strategy\nOne crucial observation is that the grid size is `k x k` and we have `k` element to fill. \nAny row and column has enough spaces to host all `k` elements.\nThis means that if there is no cycle, then we will always be able to assign a unique `row` and a unique `col` value.\nHere I use topological sort to make sure there is no cycle, and populate the order in which we should place it. \nEach number will get its unique `row` and `column` value from `0` to `k-1`.\nRun this topological once for each direction - row, column.\n\n`Time O(k^2 + R + C)`\n`Space O(k^2 + max(R, C))`\n```Java\nclass Solution {\n    public int[][] buildMatrix(int k, int[][] R, int[][] C) {\n        int[][] ans = new int[k][k];\n        int[] yp = new int[k+1]; // y position (col)\n        int[] xp = new int[k+1]; // x position (row)\n        Arrays.fill(xp, -1);\n        Arrays.fill(yp, -1);\n        if (!build(R, xp, k) || !build(C, yp, k)){ // if we can\'t build it, there is a cycle, return empty.\n            return new int[0][0];\n        }\n        for (int i = 1; i <= k; i++){ // otherwise, we fill it.\n            ans[xp[i]][yp[i]] = i;\n        }\n        return ans;\n    }\n\n    private boolean build(int[][] A, int[] pos, int k){\n        List<Integer>[] map = new ArrayList[k+1];\n        Arrays.setAll(map, o -> new ArrayList<>());\n        int[] indg = new int[k+1];\n        int depth = 0;\n        for (int[] a : A){ // build the map and the indegree.\n            map[a[0]].add(a[1]);\n            indg[a[1]]++;\n        }\n\t\t// here we enqueue all the nodes with indegree 0.\n        Deque<Integer> queue = new ArrayDeque<>(IntStream.range(1, k+1).filter(o -> indg[o] == 0).boxed().toList());\n        while(!queue.isEmpty()){\n            int y = queue.poll();\n            pos[y] = depth++; // set its depth. each value gets a unique depth.\n            for (int next : map[y]){\n                if (--indg[next] == 0){\n                    queue.offer(next);\n                }\n            }\n        }\n        if (Arrays.stream(indg).anyMatch(o -> o > 0)){\n            return false; // If there is any node with indegree > 0, then there is a cycle.\n        }\n        for (int i = 1; i <= k; i++){\n            if (pos[i] == -1){ // if there is any not filled yet, fill it\n                pos[i] = depth++;\n            }\n        }\n        return true;\n    }\n}\n```
['Topological Sort', 'Java']