2392. Build a Matrix With Conditions Hard

1/**
2 * [2392] Build a Matrix With Conditions
3 *
4 * You are given a positive integer k. You are also given:
5 * 
6 * 	a 2D integer array rowConditions of size n where rowConditions[i] = [abovei, belowi], and
7 * 	a 2D integer array colConditions of size m where colConditions[i] = [lefti, righti].
8 * 
9 * The two arrays contain integers from 1 to k.
10 * You have to build a k x k matrix that contains each of the numbers from 1 to k exactly once. The remaining cells should have the value 0.
11 * The matrix should also satisfy the following conditions:
12 * 
13 * 	The number abovei should appear in a row that is strictly above the row at which the number belowi appears for all i from 0 to n - 1.
14 * 	The number lefti should appear in a column that is strictly left of the column at which the number righti appears for all i from 0 to m - 1.
15 * 
16 * Return any matrix that satisfies the conditions. If no answer exists, return an empty matrix.
17 *  
18 * Example 1:
19 * <img alt="" src="https://assets.leetcode.com/uploads/2022/07/06/gridosdrawio.png" style="width: 211px; height: 211px;" />
20 * Input: k = 3, rowConditions = [[1,2],[3,2]], colConditions = [[2,1],[3,2]]
21 * Output: [[3,0,0],[0,0,1],[0,2,0]]
22 * Explanation: The diagram above shows a valid example of a matrix that satisfies all the conditions.
23 * The row conditions are the following:
24 * - Number 1 is in row <u>1</u>, and number 2 is in row <u>2</u>, so 1 is above 2 in the matrix.
25 * - Number 3 is in row <u>0</u>, and number 2 is in row <u>2</u>, so 3 is above 2 in the matrix.
26 * The column conditions are the following:
27 * - Number 2 is in column <u>1</u>, and number 1 is in column <u>2</u>, so 2 is left of 1 in the matrix.
28 * - Number 3 is in column <u>0</u>, and number 2 is in column <u>1</u>, so 3 is left of 2 in the matrix.
29 * Note that there may be multiple correct answers.
30 * 
31 * Example 2:
32 * 
33 * Input: k = 3, rowConditions = [[1,2],[2,3],[3,1],[2,3]], colConditions = [[2,1]]
34 * Output: []
35 * Explanation: From the first two conditions, 3 has to be below 1 but the third conditions needs 3 to be above 1 to be satisfied.
36 * No matrix can satisfy all the conditions, so we return the empty matrix.
37 * 
38 *  
39 * Constraints:
40 * 
41 * 	2 <= k <= 400
42 * 	1 <= rowConditions.length, colConditions.length <= 10^4
43 * 	rowConditions[i].length == colConditions[i].length == 2
44 * 	1 <= abovei, belowi, lefti, righti <= k
45 * 	abovei != belowi
46 * 	lefti != righti
47 * 
48 */
49pub struct Solution {}
50
51// problem: https://leetcode.com/problems/build-a-matrix-with-conditions/
52// discuss: https://leetcode.com/problems/build-a-matrix-with-conditions/discuss/?currentPage=1&orderBy=most_votes&query=
53
54// submission codes start here
55
56impl Solution {
57    pub fn build_matrix(k: i32, row_conditions: Vec<Vec<i32>>, col_conditions: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
58        vec![]
59    }
60}
61
62// submission codes end
63
64#[cfg(test)]
65mod tests {
66    use super::*;
67
68    #[test]
69    fn test_2392() {
70    }
71}
72