# 2392. Build a Matrix With Conditions

• Time: $O(|\texttt{rowConditions}| + |\texttt{colConditions}| + k)$
• Space: $O(k^2)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 class Solution { public: vector> buildMatrix(int k, vector>& rowConditions, vector>& colConditions) { const vector rowOrder = topologicalSort(rowConditions, k); if (rowOrder.empty()) return {}; const vector colOrder = topologicalSort(colConditions, k); if (colOrder.empty()) return {}; vector> ans(k, vector(k)); vector nodeToRowIndex(k + 1); for (int i = 0; i < k; ++i) nodeToRowIndex[rowOrder[i]] = i; for (int j = 0; j < k; ++j) { const int node = colOrder[j]; const int i = nodeToRowIndex[node]; ans[i][j] = node; } return ans; } private: vector topologicalSort(const vector>& conditions, int n) { vector order; vector> graph(n + 1); vector inDegree(n + 1); queue q; // Build graph for (const vector& condition : conditions) { const int u = condition[0]; const int v = condition[1]; graph[u].push_back(v); ++inDegree[v]; } // Topology for (int i = 1; i <= n; ++i) if (inDegree[i] == 0) q.push(i); while (!q.empty()) { const int u = q.front(); q.pop(); order.push_back(u); for (const int v : graph[u]) if (--inDegree[v] == 0) q.push(v); } return order.size() == n ? order : vector(); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 class Solution { public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) { List rowOrder = topologicalSort(rowConditions, k); if (rowOrder.isEmpty()) return new int[][] {}; List colOrder = topologicalSort(colConditions, k); if (colOrder.isEmpty()) return new int[][] {}; int[][] ans = new int[k][k]; int[] nodeToRowIndex = new int[k + 1]; for (int i = 0; i < k; ++i) nodeToRowIndex[rowOrder.get(i)] = i; for (int j = 0; j < k; ++j) { final int node = colOrder[j]; final int i = nodeToRowIndex[node]; ans[i][j] = node; } return ans; } private List topologicalSort(int[][] conditions, int n) { List order = new ArrayList<>(); List[] graph = new List[n + 1]; int[] inDegree = new int[n + 1]; Queue q = new ArrayDeque<>(); for (int i = 1; i <= n; ++i) graph[i] = new ArrayList<>(); // Build graph for (int[] condition : conditions) { final int u = condition[0]; final int v = condition[1]; graph[u].add(v); ++inDegree[v]; } // Topology for (int i = 1; i <= n; ++i) if (inDegree[i] == 0) q.offer(i); while (!q.isEmpty()) { final int u = q.poll(); order.add(u); for (final int v : graph[u]) if (--inDegree[v] == 0) q.offer(v); } return order.size() == n ? order : new ArrayList<>(); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 class Solution: def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]: rowOrder = self._topologicalSort(rowConditions, k) if not rowOrder: return [] colOrder = self._topologicalSort(colConditions, k) if not colOrder: return [] ans = [[0] * k for _ in range(k)] nodeToRowIndex = [0] * (k + 1) for i, node in enumerate(rowOrder): nodeToRowIndex[node] = i for j, node in enumerate(colOrder): i = nodeToRowIndex[node] ans[i][j] = node return ans def _topologicalSort(self, conditions: List[List[int]], n: int) -> List[int]: order = [] graph = [[] for _ in range(n + 1)] inDegree = [0] * (n + 1) # Build graph for u, v in conditions: graph[u].append(v) inDegree[v] += 1 # Topology q = collections.deque([i for i in range(1, n + 1) if inDegree[i] == 0]) while q: u = q.popleft() order.append(u) for v in graph[u]: inDegree[v] -= 1 if inDegree[v] == 0: q.append(v) return order if len(order) == n else []