Today I have done leetcode's November LeetCoding Challenge with cpp.

November LeetCoding Challenge 30

Description

Valid Arrangement of Pairs

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.

Solution

class Solution {
public:
  vector<vector<int>> validArrangement(vector<vector<int>>& pairs) {
    int sz = pairs.size();
    map<int, vector<int>> neighbors;
    map<int, int> degree;

    for(const auto &p : pairs) {
      neighbors[p[0]].push_back(p[1]);
      degree[p[0]] += 1;
      degree[p[1]] -= 1;
    }

    int current = neighbors.begin()->first;
    for(const auto &[p, d] : degree) {
      if(d == 1) current = p;
    }
    vector<int> path;
    vector<int> st = {current};
    while(st.size()) {
      int current = st.back();
      if(neighbors[current].empty()) {
        path.push_back(current);
        st.pop_back();
      } else {
        int next = neighbors[current].back();
        neighbors[current].pop_back();
        st.push_back(next);
      }
    }

    vector<vector<int>> answer;
    reverse(path.begin(), path.end());
    for(int i = 0; i < sz; ++i) {
      answer.push_back({path[i], path[i + 1]});
    }
    return answer;
  }
};