aboutsummaryrefslogtreecommitdiff
path: root/other/build_matrix_conditions.cpp
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-03-10 00:36:13 -0600
committerJack Sangdahl <[email protected]>2025-03-10 00:36:13 -0600
commit7c60dee83b436e8e8a667bf9f191beced8de4fc3 (patch)
treeeb7a24ee2067f92245c57bb118e85a1baf15df50 /other/build_matrix_conditions.cpp
parent5d7cdc215e4ba1ec4cbb24c084cccb5e5e641468 (diff)
downloadleetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.tar.gz
leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.zip
chore: move cpp and rust code to directory
Diffstat (limited to 'other/build_matrix_conditions.cpp')
-rw-r--r--other/build_matrix_conditions.cpp98
1 files changed, 98 insertions, 0 deletions
diff --git a/other/build_matrix_conditions.cpp b/other/build_matrix_conditions.cpp
new file mode 100644
index 0000000..e192dda
--- /dev/null
+++ b/other/build_matrix_conditions.cpp
@@ -0,0 +1,98 @@
+// 2392. Build a Matrix With Conditions
+#include "leetcode.h"
+
+/*
+ * you are givne a positive integer 'k'. you are also given a 2d integer array
+ * 'rowConditions' of size 'n' where 'rowConditions[i] = [above_i, below_i]' and
+ * a 2d integer array 'colConditions' of size 'm' where 'colConditions[i] =
+ * [left_i, right_i]'. the two arrays contain integers from 1 to 'k'. you have
+ * to build a 'k * k' matrix that contains each of the numbers from 1 to 'k'
+ * exactly once. the remaining cells should satisfy the following conditions.
+ * the number 'above_i' should appear in a row that is strictly above the row at
+ * which the number 'below_i' appears for all 'i'. the number 'left_i' should
+ * appear in a column that is strictly left of the column at which the number
+ * 'right_i' appears for all 'i'. return any matrix that satisfies these
+ * conditions.
+ */
+
+class Solution {
+private:
+ vector<char> colour;
+ vector<bool> visited;
+ bool dfs(int v, vector<vector<int>> &graph) {
+ colour[v] = 1;
+ for (int i : graph[v]) {
+ if (!colour[i]) {
+ if (dfs(i, graph))
+ return true;
+ } else if (colour[i] == 1)
+ return true;
+ }
+ colour[v] = 2;
+ return false;
+ }
+ bool find_cycle(vector<vector<int>> &graph, int n) {
+ colour.assign(n, 0);
+ for (int i = 0; i < n; i++)
+ if (!colour[i] && dfs(i, graph))
+ return true;
+ return false;
+ }
+ void dfs2(int v, vector<vector<int>> &graph, vector<int> &res) {
+ visited[v] = true;
+ for (int i : graph[v])
+ if (!visited[i])
+ dfs2(i, graph, res);
+ res.push_back(v);
+ }
+ void topo_sort(vector<vector<int>> &graph, int n, vector<int> &res) {
+ visited.assign(n, false);
+ res.clear();
+ for (int i = 0; i < n; ++i)
+ if (!visited[i])
+ dfs2(i, graph, res);
+ reverse(res.begin(), res.end());
+ }
+
+public:
+ vector<vector<int>> buildMatrix(int k, vector<vector<int>> &rowConditions,
+ vector<vector<int>> &colConditions) {
+ vector<vector<int>> g1(k), g2(k);
+ for (auto i : rowConditions)
+ g1[i[0] - 1].push_back(i[1] - 1);
+ for (auto i : colConditions)
+ g2[i[0] - 1].push_back(i[1] - 1);
+ if (find_cycle(g1, k) || find_cycle(g2, k))
+ return vector<vector<int>>();
+ vector<int> a1, a2;
+ topo_sort(g1, k, a1);
+ topo_sort(g1, k, a2);
+ vector<vector<int>> ans(k, vector<int>(k));
+ map<int, int> m;
+ for (int i = 0; i < k; i++)
+ m[a2[i]] = i;
+ for (int i = 0; i < k; i++)
+ ans[i][m[a1[i]]] = a1[i] + 1;
+ return ans;
+ }
+};
+
+int main() {
+ Solution obj;
+ vvd rc1 = {{1, 2}, {3, 2}}, cc1 = {{2, 1}, {3, 2}};
+ vvd rc2 = {{1, 2}, {2, 3}, {3, 1}, {2, 3}}, cc2 = {{2, 1}};
+ vvd bm1 = obj.buildMatrix(3, rc1, cc1),
+ bm2 = obj.buildMatrix(3, rc2, cc2);
+ for (int i = 0; i < bm1.size(); i++) {
+ for (int j = 0; j < bm1[0].size(); j++)
+ printf("%d ", bm1[i][j]);
+ printf("\n");
+ }
+ printf("\n");
+ for (int i = 0; i < bm2.size(); i++) {
+ for (int j = 0; j < bm2[0].size(); j++)
+ printf("%d ", bm2[i][j]);
+ printf("\n");
+ }
+ printf("\n");
+}