Topological Sort (w/ Comments)
Intuition\n Describe your first thoughts on how to solve this problem. \nDetermine what number has no numbers before it at any time.\n\n# Approach\n Describe yo
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nDetermine what number has no numbers before it at any time.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nCreate a dictionary of what numbers precede any number.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(k^2)$$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(k^2)$$\n\n# Code\n```\npublic class Solution {\n    private int k;\n    public int[][] BuildMatrix(int k, int[][] rowConditions, int[][] colConditions) {\n        this.k = k;\n\n        // Get positions of all numbers\n        int[] row_positions = GetPositions(rowConditions);\n        int[] column_positions = GetPositions(colConditions);\n\n        // Check that there are no cycles\n        if (row_positions == null || column_positions == null)\n            return new int[0][];\n\n        // Create 2-d array\n        int[][] result = new int[k][];\n        for (int i = 0; i < k; i++) {\n            result[i] = new int[k];\n        }\n\n        // Put all number into their spots\n        for (int i = 1; i <= k; i++) {\n            result[row_positions[i]][column_positions[i]] = i;\n        }\n\n        return result;\n    }\n\n    private int[] GetPositions(int[][] conditions) {\n        // Keep a dict of numbers that are before and after other numbers\n        Dictionary<int, HashSet<int>> befores = new Dictionary<int, HashSet<int>>();\n        Dictionary<int, HashSet<int>> afters = new Dictionary<int, HashSet<int>>();\n\n        // Add all numbers as keys into the dictionaries\n        for (int i = 1; i <= this.k; i++) {\n            befores.Add(i, new HashSet<int>());\n            afters.Add(i, new HashSet<int>());\n        }\n\n        // Populate dictionaries\n        foreach (int[] condition in conditions) {\n            int before = condition[0];\n            int after = condition[1];\n\n            befores[after].Add(before);\n            afters[before].Add(after);  \n        }\n\n        int[] order = new int[k+1];\n        int position = 0;\n        while (befores.Count > 0) {\n            // Find the element with the least # of elements before it\n            int next_key = -1;\n            int next_count = Int32.MaxValue;\n            foreach (var pair in befores) {\n                if (pair.Value.Count < next_count) {\n                    next_key = pair.Key;\n                    next_count = pair.Value.Count;\n                }\n            }\n\n            // Remove this number from all after\'s before list\n            foreach (int after in afters[next_key])\n                if (befores.ContainsKey(after))\n                    befores[after].Remove(next_key);\n                else\n                    return null;        // Cycle detected\n                    // known because a number after the current one\n                    // has already been placed before this one\n\n            // Give this number a position in the matrix\n            order[next_key] = position++;\n\n            // Remove this number from the befores list\n            befores.Remove(next_key);\n        }\n\n        return order;\n    }\n}\n```
['C#']