2097. Valid Arrangement of Pairs

Posted on Edited on In

2097. Valid Arrangement of Pairs

Description

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:

1
2
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:

1
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:

1
2
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 <= 10^5
  • pairs[i].length == 2
  • 0 <= start<sub>i</sub>, end<sub>i</sub> <= 10^9
  • start<sub>i</sub> != end<sub>i</sub>
  • No two pairs are exactly the same.
  • There exists a valid arrangement of pairs.

Hints/Notes

Solution

Language: 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    unordered_map<int, deque<int>> matrix;
    unordered_map<int, int> inDegree, outDegree;
    vector<int> path;
    vector<vector<int>> validArrangement(vector<vector<int>>& pairs) {
        int n = pairs.size();
        for (int i = 0; i < n; i++) {
            int start = pairs[i][0], end = pairs[i][1];
            matrix[start].push_back(end);
            outDegree[start]++;
            inDegree[end]++;
        }
        int startPoint = -1;
        for (auto& [k, _] : outDegree) {
            if (inDegree[k] < outDegree[k]) {
                startPoint = k;
                break;
            }
        }
        if (startPoint == -1) {
            startPoint = pairs[0][0];
        }
        dfs(startPoint);
        ranges::reverse(path);
        vector<vector<int>> res;
        for (int i = 0; i < path.size() - 1; i++) {
            res.push_back({path[i], path[i + 1]});
        }

        return res;
    }

    void dfs(int node) {
        while (!matrix[node].empty()) {
            int nextNode = matrix[node].front();
            matrix[node].pop_front();
            dfs(nextNode);
        }
        path.push_back(node);
    }
};