diff options
-rw-r--r-- | valid_arrangement_pairs.cpp | 73 | ||||
-rw-r--r-- | valid_arrangement_pairs.py | 44 |
2 files changed, 117 insertions, 0 deletions
diff --git a/valid_arrangement_pairs.cpp b/valid_arrangement_pairs.cpp new file mode 100644 index 0000000..f1f8b20 --- /dev/null +++ b/valid_arrangement_pairs.cpp @@ -0,0 +1,73 @@ +// 2097. Valid Arrangement of Pairs +#include "leetcode.h" + +/* + * you are given a 0-indexed 2d integer array 'pairs' where 'pairs[i] = + * [start_i, end_i]'. an arrangement of 'pairs' is valid for every index 'i' + * where '1 <= i < pairs.length', we have 'end_i-1 == start_i'. return any valid + * arrangement of 'pairs'. note, the inputs will be generated such that there + * exists a valid arrangement of 'pairs'. + */ + +class Solution { +private: + void euler(unordered_map<int, stack<int>> &adj, vector<vector<int>> &res, + int curr) { + auto &st = adj[curr]; + while (!st.empty()) { + int n = st.top(); + st.pop(); + euler(adj, res, n); + res.push_back({curr, n}); + } + } + +public: + vector<vector<int>> validArrangement(vector<vector<int>> &pairs) { + int m = pairs.size(); + unordered_map<int, stack<int>> adj; + unordered_map<int, int> in, out; + adj.reserve(m); + in.reserve(m); + out.reserve(m); + for (int i = 0; i < m; i++) { + int u = pairs[i][0], v = pairs[i][1]; + in[v]++; + out[u]++; + adj[u].push(v); + } + int start = -1; + for (auto &p : adj) { + int i = p.first; + if (out[i] - in[i] == 1) + start = i; + } + if (start == -1) + start = adj.begin()->first; + vector<vector<int>> ans; + euler(adj, ans, start); + reverse(ans.begin(), ans.end()); + return ans; + } +}; + +int main() { + Solution obj; + vvd(int) p1 = {{5, 1}, {4, 5}, {11, 9}, {9, 4}}, + p2 = {{1, 3}, {3, 2}, {2, 1}}, p3 = {{1, 2}, {1, 3}, {2, 1}}; + vvd(int) va1 = obj.validArrangement(p1); + vvd(int) va2 = obj.validArrangement(p2); + vvd(int) va3 = obj.validArrangement(p3); + for (int i = 0; i < va1.size(); i++) + for (int j = 0; j < va1[0].size(); j++) + printf("%d ", va1[i][j]); // expect: [[11,9],[9,4],[4,5],[5,1]] + printf("\n"); + for (int i = 0; i < va2.size(); i++) + for (int j = 0; j < va2[0].size(); j++) + printf("%d ", va2[i][j]); // expect: [[1,3],[3,2],[2,1]] + printf("\n"); + for (int i = 0; i < va3.size(); i++) + for (int j = 0; j < va3[0].size(); j++) + printf("%d ", va1[i][j]); // expect: [[1,2],[2,1],[1,3]] + printf("\n"); +} diff --git a/valid_arrangement_pairs.py b/valid_arrangement_pairs.py new file mode 100644 index 0000000..528c883 --- /dev/null +++ b/valid_arrangement_pairs.py @@ -0,0 +1,44 @@ +# 2097. Valid Arrangement of Pairs +from collections import defaultdict + +""" +you are given a 0-indexed 2d integer array 'pairs' where 'pairs[i] = +[start_i, end_i]'. an arrangement of 'pairs' is valid for every index 'i' +where '1 <= i < pairs.length', we have 'end_i-1 == start_i'. return any valid +arrangement of 'pairs'. note, the inputs will be generated such that there +exists a valid arrangement of 'pairs'. +""" + + +class Solution(object): + def validArrangement(self, pairs): + """ + :type pairs: List[List[int]] + :rtype: List[List[int]] + """ + graph, degree = defaultdict(list), defaultdict(int) + for x, y in pairs: + graph[x].append(y) + degree[x] += 1 + degree[y] -= 1 + for k in degree: + if degree[k] == 1: + x = k + break + ans = [] + + def euler(x): + while graph[x]: + euler(graph[x].pop()) + ans.append(x) + + euler(x) + ans.reverse() + return [[ans[i], ans[i + 1]] for i in range(len(ans) - 1)] + + +if __name__ == "__main__": + obj = Solution() + print(obj.validArrangement(pairs=[[5, 1], [4, 5], [11, 9], [9, 4]])) + print(obj.validArrangement(pairs=[[1, 3], [3, 2], [2, 1]])) + print(obj.validArrangement(pairs=[[1, 2], [1, 3], [2, 1]])) |