Java BFS solution
Explanation\nBoth left to right and above to below form directed graphs. We apply topological sort to both these graphs. If we detect a cycle in either directed
# Explanation\nBoth left to right and above to below form directed graphs. We apply topological sort to both these graphs. If we detect a cycle in either directed graph, we return an empty matrix. We use a map to map a number to its to indicices provided from both\'s topological sort. We fill the matrix at these indices with its number. Since we only loop through the indices, rowConditions and colConditions; the time complexity is O(k + R + C). \n\nFor example,\nConsider: left to right topological sorted: 3 -> 2 -> 1 -> 4 -> 5\nand the above to below topological sorted: 4 -> 5 -> 3 -> 3 -> 1\n\n        3    2   1   4   5  \n\n    4                x\n\n    5                    x\n\n    3  x  \n\n    2       x\n\n    1           x\n\nThe x\'s mark the indices intersection of left to right and above to below. We add the number to these indices in the matrix. \nThe x occurs when the left to right index value has the same value as the above to below index value.\n\n# Code\n```\nclass Solution {\n    public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {\n        \n        Map<Integer, List<Integer>> mapRowConditions = new HashMap<>();\n        Map<Integer, List<Integer>> mapColConditions = new HashMap<>();\n\n        int[] inDegreesBelow = new int[k + 1];\n        int[] inDegreesRight = new int[k + 1];\n\n        Queue<Integer> qRowConditions = new LinkedList<>();\n        Queue<Integer> qColConditions = new LinkedList<>();\n\n        Map<Integer, List<Integer>> mapNumToIndices = new HashMap<>();\n\n        for (int i = 0; i < rowConditions.length; i++) {\n            int above = rowConditions[i][0];\n            int below = rowConditions[i][1];\n            if (!mapRowConditions.containsKey(above)) {\n                mapRowConditions.put(above, new ArrayList<>());\n            }\n            mapRowConditions.get(above).add(below);\n            inDegreesBelow[below]++;\n        }\n\n         for (int i = 0; i < colConditions.length; i++) {\n            int left = colConditions[i][0];\n            int right = colConditions[i][1];\n            if (!mapColConditions.containsKey(left)) {\n                mapColConditions.put(left, new ArrayList<>());\n            }\n            mapColConditions.get(left).add(right);\n            inDegreesRight[right]++;\n        }\n\n        for (int i = 1; i < k + 1; i++) {\n\n            if (inDegreesBelow[i] == 0) qRowConditions.add(i);\n            if (inDegreesRight[i] == 0) qColConditions.add(i);\n            mapNumToIndices.put(i, new ArrayList<>());\n\n        }\n\n\n        int index = 0;\n        while (!qRowConditions.isEmpty()) {\n            int leaf = qRowConditions.poll();\n            mapNumToIndices.get(leaf).add(index);\n            index++;\n            if (!mapRowConditions.containsKey(leaf)) continue;\n            List<Integer> listBelow = mapRowConditions.get(leaf);\n            for (int i = 0; i < listBelow.size(); i++) {\n                int below = listBelow.get(i);\n                inDegreesBelow[below]--;\n                if (inDegreesBelow[below] == 0) qRowConditions.add(below);\n            }\n        }\n        if (index != k) return new int[][]{};\n        index = 0;\n        while (!qColConditions.isEmpty()) {\n            int leaf = qColConditions.poll();\n            mapNumToIndices.get(leaf).add(index);\n            index++;\n            if (!mapColConditions.containsKey(leaf)) continue;\n            List<Integer> listRight = mapColConditions.get(leaf);\n            for (int i = 0; i < listRight.size(); i++) {\n                int right = listRight.get(i);\n                inDegreesRight[right]--;\n                if (inDegreesRight[right] == 0) qColConditions.add(right);\n            }\n        }\n        if (index != k) return new int[][]{};\n        \n        int[][] result = new int[k][k];\n        for (int i = 1; i < k + 1; i++) {\n\n            List<Integer> yx = mapNumToIndices.get(i);\n            int y = yx.get(0);\n            int x = yx.get(1);\n            result[y][x] = i;\n\n        }\n\n        return result;\n\n    }\n}\n```
['Java']