-
Notifications
You must be signed in to change notification settings - Fork 0
/
BuildAMatrixWithConditions.java
54 lines (51 loc) · 1.92 KB
/
BuildAMatrixWithConditions.java
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
/* https://leetcode.com/problems/build-a-matrix-with-conditions/?envType=daily-question&envId=2024-07-21 */
/* 2392. Build a Matrix With Conditions */
class BuildAMatrixWithConditions {
private int size;
public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {
this.size = k;
List<Integer> rowOrder = getOrder(rowConditions);
List<Integer> colOrder = getOrder(colConditions);
if (rowOrder == null || colOrder == null) {
return new int[0][0];
}
int[][] matrix = new int[size][size];
int[] columnMapping = new int[size + 1];
for (int i = 0; i < size; ++i) {
columnMapping[colOrder.get(i)] = i;
}
for (int i = 0; i < size; ++i) {
matrix[i][columnMapping[rowOrder.get(i)]] = rowOrder.get(i);
}
return matrix;
}
private List<Integer> getOrder(int[][] conditions) {
// Graph to represent conditions
List<Integer>[] graph = new List[size + 1];
// Initialize lists for all vertices in the graph
Arrays.setAll(graph, element -> new ArrayList<>());
int[] incomingEdges = new int[size + 1];
for (var edge : conditions) {
int from = edge[0], to = edge[1];
graph[from].add(to);
++incomingEdges[to];
}
Deque<Integer> queue = new ArrayDeque<>();
for (int i = 1; i <= size; ++i) {
if (incomingEdges[i] == 0) {
queue.offer(i);
}
}
List<Integer> order = new ArrayList<>();
while (!queue.isEmpty()) {
int vertex = queue.pollFirst();
order.add(vertex);
for (int neighbour : graph[vertex]) {
if (--incomingEdges[neighbour] == 0) {
queue.offer(neighbour);
}
}
}
return order.size() == size ? order : null;
}
}