leetcode

commit cb13a928c30437e4c11bab9084b3fb3deaa838d2
parent f6f1bbdc52b33ced7eb454ab498b777426855135
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 21 Jul 2024 21:13:08 +0200

Daily Problem

Diffstat:
A
Problems/2392.cpp
 | 
52
++++++++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 53 insertions(+), 0 deletions(-)
diff --git a/Problems/2392.cpp b/Problems/2392.cpp
@@ -0,0 +1,52 @@
+class Solution {
+    static vector<int> create(int k, const vector<vector<int>> &conditions) {
+        vector<vector<int>> adj(k + 1);
+        static int count[402];
+
+        memset(count, 0x00, sizeof(count));
+        for (const auto &row : conditions) {
+            adj[row[0]].push_back(row[1]);
+            count[row[1]]++;
+        }
+
+        queue<int> q;
+        for (int i = 1; i <= k; i++) {
+            if (count[i] != 0) continue;
+            q.push(i);
+        }
+
+        if (q.empty()) return {};
+
+        int cnt = 0;
+        vector<int> res(k + 1, -1);
+        while (!q.empty()) {
+            const auto crnt = q.front();
+            q.pop();
+
+            for (const int below : adj[crnt]) {
+                if (--count[below] != 0) continue;
+                q.push(below);
+            }
+
+            res[crnt] = cnt++;
+        }
+
+        return cnt == k ? res : vector<int>();
+    }
+
+  public:
+    vector<vector<int>> buildMatrix(int k, const vector<vector<int>> &rowConditions,
+                                    const vector<vector<int>> &colConditions) const {
+        const auto row = create(k, rowConditions);
+        if (row.empty()) return {};
+
+        const auto col = create(k, colConditions);
+        if (col.empty()) return {};
+
+        vector<vector<int>> res(k, vector(k, 0));
+        for (int i = 1; i <= k; i++)
+            res[row[i]][col[i]] = i;
+
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -1152,6 +1152,7 @@ for solving problems.
 |  2385  |   Medium   | [Amount of Time for Binary Tree to Be Infected](Problems/2385.cpp)                                 |
 |  2390  |   Medium   | [Removing Stars From a String](Problems/2390.cpp)                                                  |
 |  2391  |   Medium   | [Minimum Amount of Time to Collect Garbage](Problems/2391.cpp)                                     |
+|  2392  |    Hard    | [Build a Matrix With Conditions](Problems/2392.cpp)                                                |
 |  2396  |   Medium   | [Strictly Palindromic Number](Problems/2396.cpp)                                                   |
 |  2397  |   Medium   | [Maximum Rows Covered by Columns](Problems/2397.cpp)                                               |
 |  2401  |   Medium   | [Longest Nice Subarray](Problems/2401.cpp)                                                         |