Valid Arrangement of Pairs - Video Solutions

Problem Overview: You receive pairs[i] = [start, end]. Rearrange the pairs so that the end of one pair equals the start of the next. Every pair must be used exactly once. The task reduces to finding an ordering of directed edges that forms a continuous chain.

Approach 1: Backtracking / Permutation Search (O(n!))

Treat each pair as a directed edge and attempt to build the sequence using brute-force backtracking. Start from any pair, then recursively choose another unused pair whose start matches the current end. Track visited pairs and build the path step by step. This guarantees correctness but explores up to n! permutations in the worst case, with O(n) recursion space. This approach only works for very small inputs and mainly helps recognize the structure of the chaining requirement.

Approach 2: Eulerian Path in Directed Graph (Hierholzer’s Algorithm) (O(n))

Interpret each pair as a directed edge in a graph. The problem becomes finding an Eulerian path that uses every edge exactly once. Maintain an adjacency list mapping start → list of ends and compute in-degrees and out-degrees. A valid arrangement exists when either every node has equal in/out degree (Eulerian circuit) or exactly one node has out = in + 1 (start node) and one has in = out + 1. Use Depth-First Search with Hierholzer’s algorithm: repeatedly follow edges, removing them as you traverse, and append nodes during backtracking. The reversed traversal order forms the valid edge sequence. Time complexity is O(n) since each edge is processed once, and space complexity is O(n) for adjacency storage and recursion.

Approach 3: Iterative Hierholzer Using Stack (O(n))

The same Eulerian-path logic can be implemented iteratively using a stack instead of recursion. Push the start node onto the stack and keep traversing unused outgoing edges while pushing nodes. When a node has no remaining edges, pop it and append it to the path. This produces the Eulerian traversal in reverse order. The algorithm still processes each edge once, so time complexity remains O(n) with O(n) auxiliary space. Some engineers prefer this approach to avoid recursion limits.

Recommended for interviews: The Eulerian path solution using Hierholzer’s algorithm is the expected answer. Interviewers want you to recognize that the chaining constraint maps directly to an Eulerian Circuit / Path problem in a directed graph. Mentioning the brute-force idea shows you understand the search space, but implementing the linear-time graph solution demonstrates strong algorithmic insight.