2097

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:

• Reconstruct Itinerary (Hard)
• Find if Path Exists in Graph (Easy)

Solution 1. Eulerian Circuit

// OJ: https://leetcode.com/problems/valid-arrangement-of-pairs/
// Author: github.com/lzl124631x
// 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[0], v = e[1];
            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;
    }
};