Valid Arrangement of Pairs

Leetcode Problem:

• Valid Arrangement of Pairs

Summary

• Find a valid arrangement of pairs where each pair is connected to the previous one

Approach

• Use a depth-first search (DFS) to traverse the graph of pairs, starting from the node with the highest degree
• The DFS visits all nodes in the graph and constructs a path in reverse order

Complexity

• O(n + e), where n is the number of pairs and e is the number of edges

Explanation

• The solution first builds an adjacency list and degree map to represent the graph of pairs
• It then finds the node with the highest degree, which is the starting point for the DFS
• The DFS visits all nodes in the graph and constructs a path in reverse order, which represents a valid arrangement of pairs

Solution Code:

class Solution {
public:
    unordered_map> adj;
    unordered_map deg;

    vector rpath;
    void euler(int i){
        vector stk={i};
        while(!stk.empty()){
            i = stk.back();
            if(adj[i].empty()){
                rpath.push_back(i);
                stk.pop_back();
            } else{
                int j = adj[i].back();
                adj[i].pop_back();
                stk.push_back(j);
            }
        }
    }

    vector> validArrangement(vector>& pairs) {
        const int e = pairs.size();
        adj.reserve(e);
        deg.reserve(e);

        for(auto& edge : pairs){
            int start = edge[0], end=edge[1];
            adj[start].push_back(end);
            deg[start]++;
            deg[end]--;
        }

        int i0=deg.begin()->first;
        for (auto& [v,d]: deg){
            if(d == 1){
                i0 = v;
                break;
            }
        }
        euler(i0);

        vector> ans;
        ans.reserve(e);

        for(int i = rpath.size() - 2; i >= 0 ; i--){
            ans.push_back({rpath[i+1], rpath[i]});
        }
        return ans;

    }
};