Formatted question description: https://leetcode.ca/all/2097.html

# 2097. Valid Arrangement of Pairs (Hard)

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 <= 105
• pairs[i].length == 2
• 0 <= starti, endi <= 109
• starti != endi
• No two pairs are exactly the same.
• There exists a valid arrangement of pairs.

Related Topics:
Depth-First Search, Graph, Eulerian Circuit

Similar Questions:

## Solution 1. Eulerian Circuit

// OJ: https://leetcode.com/problems/valid-arrangement-of-pairs/
// Time: O(N + U) where N is the number of pairs and U is the number of unique numbers in the pairs
// Space: O(N + U)
// Ref: https://leetcode.com/problems/valid-arrangement-of-pairs/discuss/1611978/C%2B%2B-Eulerian-Path-with-Explanation
class Solution {
public:
vector<vector<int>> validArrangement(vector<vector<int>>& E) {
int N = E.size();
unordered_map<int, vector<int>> G;
unordered_map<int, int> indegree, outdegree;
G.reserve(N);
indegree.reserve(N);
outdegree.reserve(N);
for (auto &e : E) {
int u = e, v = e;
outdegree[u]++;
indegree[v]++;
G[u].push_back(v);
}
int start = -1;
for (auto &[u, vs] : G) {
if (outdegree[u] - indegree[u] == 1) {
start = u; // If there exists one node u that outdegree[u] = indegree[u] + 1, use u as the start node.
break;
}
}
if (start == -1) start = G.begin()->first; // If there doesn't exist such node u, use any node as the start node
vector<vector<int>> ans;
function<void(int)> euler = [&](int u) {
auto &vs = G[u];
while (vs.size()) {
int v = vs.back();
vs.pop_back();
euler(v);
ans.push_back({ u, v }); // Post-order DFS. The edge is added after node v is exhausted
}
};
euler(start);
reverse(begin(ans), end(ans)); // Need to reverse the answer array in the end.
return ans;
}
};