leetcode

commit ebb7598f67630b4635caca530d517d57552ef404
parent 5104fc73718d42f9e5df45373a78fa4b195e8e28
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat, 30 Nov 2024 15:36:47 +0100

Daily Problem

Diffstat:
A
Problems/2097.cpp
 | 
39
+++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 40 insertions(+), 0 deletions(-)
diff --git a/Problems/2097.cpp b/Problems/2097.cpp
@@ -0,0 +1,39 @@
+class Solution {
+  public:
+    vector<vector<int>> validArrangement(const vector<vector<int>> &pairs) const {
+        unordered_map<int, int> in, out, count;
+        unordered_map<int, vector<int>> adj;
+
+        for (const auto &p : pairs) {
+            adj[p[0]].push_back(p[1]);
+            out[p[0]]++, in[p[1]]++;
+        }
+
+        int start = pairs[0][0];
+        for (const auto &[v, _] : adj) {
+            if (out[v] - in[v] != 1) continue;
+            start = v;
+            break;
+        }
+
+        stack<int> st;
+        vector<int> res;
+        for (st.push(start); !st.empty();) {
+            const int crnt = st.top();
+
+            if (count[crnt] != size(adj[crnt])) {
+                st.push(adj[crnt][count[crnt]++]);
+            } else {
+                res.push_back(crnt);
+                st.pop();
+            }
+        }
+
+        vector<vector<int>> pair_res;
+        for (int i = size(res) - 2; i >= 0; i--) {
+            pair_res.push_back({res[i + 1], res[i]});
+        }
+
+        return pair_res;
+    }
+};
diff --git a/README.md b/README.md
@@ -1192,6 +1192,7 @@ reference and a base for solving problems.
 |  2092  |    Hard    | [Find All People With Secret](Problems/2092.cpp)                                                   |
 |  2095  |   Medium   | [Delete the Middle Node of a Linked List](Problems/2095.cpp)                                       |
 |  2096  |   Medium   | [Step-By-Step Directions From a Binary Tree Node to Another](Problems/2096.cpp)                    |
+|  2097  |    Hard    | [Valid Arrangement of Pairs](Problems/2097.cpp)                                                    |
 |  2100  |   Medium   | [Find Good Days to Rob the Bank](Problems/2100.cpp)                                                |
 |  2101  |   Medium   | [Detonate the Maximum Bombs](Problems/2101.cpp)                                                    |
 |  2104  |   Medium   | [Sum of Subarray Ranges](Problems/2104.cpp)                                                        |