You are given a 0-indexed 2D integer array pairs where pairs[i] = [starti, endi]. An arrangement of pairs is valid if for every index i where 1 <= i < pairs.length, we have endi-1 == starti.
Return any valid arrangement of pairs.
Note: The inputs will be generated such that there exists a valid arrangement of pairs.
Example 1:
Input: pairs = [[5,1],[4,5],[11,9],[9,4]] Output: [[11,9],[9,4],[4,5],[5,1]] Explanation: This is a valid arrangement since endi-1 always equals starti. end0 = 9 == 9 = start1 end1 = 4 == 4 = start2 end2 = 5 == 5 = start3
Example 2:
Input: pairs = [[1,3],[3,2],[2,1]] Output: [[1,3],[3,2],[2,1]] Explanation: This is a valid arrangement since endi-1 always equals starti. end0 = 3 == 3 = start1 end1 = 2 == 2 = start2 The arrangements [[2,1],[1,3],[3,2]] and [[3,2],[2,1],[1,3]] are also valid.
Example 3:
Input: pairs = [[1,2],[1,3],[2,1]] Output: [[1,2],[2,1],[1,3]] Explanation: This is a valid arrangement since endi-1 always equals starti. end0 = 2 == 2 = start1 end1 = 1 == 1 = start2
Constraints:
1 <= pairs.length <= 105pairs[i].length == 20 <= starti, endi <= 109starti != endi- No two pairs are exactly the same.
- There exists a valid arrangement of
pairs.
Solution: Eulerian trail
The goal of the problem is to find a Eulerian trail in the graph.
If there is a vertex whose out degree – in degree == 1 which means it’s the starting vertex. Otherwise wise, the graph must have a Eulerian circuit thus we can start from any vertex.
We can use Hierholzer’s algorithm to find it.
Time complexity: O(|V| + |E|)
Space complexity: O(|V| + |E|)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
// Author: Huahua class Solution { public: vector<vector<int>> validArrangement(vector<vector<int>>& pairs) { unordered_map<int, queue<int>> g; unordered_map<int, int> degree; // out - in for (const auto& p : pairs) { g[p[0]].push(p[1]); ++degree[p[0]]; --degree[p[1]]; } int s = pairs[0][0]; for (const auto& [u, d] : degree) if (d == 1) s = u; vector<vector<int>> ans; function<void(int)> dfs = [&](int u) { while (!g[u].empty()) { int v = g[u].front(); g[u].pop(); dfs(v); ans.push_back({u, v}); } }; dfs(s); return {rbegin(ans), rend(ans)}; } }; |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
# Author: Huahua class Solution: def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]: g = defaultdict(list) d = defaultdict(int) for u, v in pairs: g[u].append(v) d[u] += 1 d[v] -= 1 s = pairs[0][0] for u in d: if d[u] == 1: s = u ans = [] def dfs(u: int) -> None: while g[u]: v = g[u].pop() dfs(v) ans.append([u, v]) dfs(s) return ans[::-1] |