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 <= 105pairs[i].length == 20 <= starti, endi <= 109starti != endipairs.The key idea behind solving #2097 Valid Arrangement of Pairs is to model the pairs as a directed graph. Each pair [u, v] represents an edge from node u to node v. The task then becomes finding an ordering of edges such that the end of one pair matches the start of the next, which closely resembles finding an Eulerian path in a directed graph.
To achieve this, track the in-degree and out-degree of each node. If a valid arrangement exists, the graph will either have an Eulerian circuit (all nodes balanced) or an Eulerian path (one node with out-degree − in-degree = 1 and another with the opposite).
After identifying the correct starting node, apply Hierholzer’s algorithm using Depth-First Search (DFS) and an adjacency list. Edges are consumed while traversing, ensuring every pair is used exactly once. The resulting traversal, built in reverse order, forms the required arrangement.
Time Complexity: O(E) where E is the number of pairs. Space Complexity: O(V + E) for storing the graph and recursion/stack.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Eulerian Path using DFS (Hierholzer’s Algorithm) | O(E) | O(V + E) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Could you convert this into a graph problem?
Consider the pairs as edges and each number as a node.
We have to find an Eulerian path of this graph. Hierholzer’s algorithm can be used.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, graph traversal and Eulerian path problems appear in advanced coding interviews, including FAANG-style interviews. This problem tests understanding of graph modeling, DFS, and edge-based traversal algorithms.
The problem requires arranging pairs so each edge connects seamlessly to the next. This matches the definition of an Eulerian path, where every edge in a graph is visited exactly once while respecting direction in a directed graph.
The optimal approach models the pairs as edges of a directed graph and finds an Eulerian path. Using Hierholzer’s algorithm with DFS allows you to traverse every edge exactly once while maintaining the required order.
An adjacency list is the most suitable data structure for representing the graph efficiently. Additionally, hash maps or dictionaries are commonly used to store adjacency lists and track in-degree and out-degree counts.