Skip to main content
Talentd

Valid Arrangement of Pairs - Solution & Explanation

HardDepth-First SearchGraphEulerian Circuit4 min readAsked at: Amazon, Goldman Sachs, Google
Practice this problem

Problem Statement

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.

Approach Overview

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.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtracking / Permutation SearchO(n!)O(n)Conceptual baseline or very small inputs
DFS Hierholzer (Eulerian Path)O(n)O(n)Optimal approach for directed graph edge ordering
Iterative Hierholzer with StackO(n)O(n)Preferred when avoiding recursion depth limits

Video Solution

Hierholzer's Algorithm | Valid Arrangement of Pairs | Leetcode 2097 | Graph Concepts & Qns - 43 • codestorywithMIK • 17,898 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Valid Arrangement of Pairs easy or hard?
Valid Arrangement of Pairs is classified as a Hard problem because it requires recognizing the Eulerian path pattern in a directed graph. The implementation itself is manageable once the graph insight is identified, but many candidates struggle to connect the problem to Hierholzer’s algorithm.
Valid Arrangement of Pairs Python/Java solution
Python and Java implementations both follow the same structure: build an adjacency list, compute degrees, determine the start node, and run DFS using Hierholzer’s algorithm. Python often uses defaultdict(list) for adjacency, while Java commonly uses HashMap<Integer, Deque<Integer>> or similar structures.
How to solve Valid Arrangement of Pairs in O(n)?
Build a directed adjacency list from the pairs and compute in-degree and out-degree for every node. Identify the correct start node (the one with out-degree = in-degree + 1 if it exists). Run Hierholzer’s DFS algorithm to traverse and remove edges while building the path. Reverse the traversal order to produce the valid pair arrangement in linear time.
What is the best approach for Valid Arrangement of Pairs?
The best approach models the pairs as edges in a directed graph and finds an Eulerian path using Hierholzer’s algorithm. Each pair becomes an edge from start to end, and the task is to traverse every edge exactly once. By tracking in-degree and out-degree and performing DFS traversal, the valid ordering can be constructed in O(n) time and O(n) space.
Is Valid Arrangement of Pairs asked at Google/Amazon/Meta?
Graph traversal and Eulerian path problems appear frequently in interviews at companies like Google, Amazon, and Meta. While this exact problem may vary in wording, recognizing when a problem reduces to an Eulerian path in a directed graph is a common interview skill tested in senior-level algorithm rounds.
What data structure is used in Valid Arrangement of Pairs?
The solution uses a graph represented by an adjacency list, typically implemented with a hash map mapping each node to a list or stack of outgoing neighbors. Additional hash maps or arrays track in-degrees and out-degrees. A recursion stack or explicit stack supports the DFS traversal used in Hierholzer’s algorithm.
What is the time complexity of Valid Arrangement of Pairs?
The optimal solution runs in O(n) time where n is the number of pairs. Each edge is added to the adjacency list once and traversed exactly once during Hierholzer’s DFS traversal. Space complexity is also O(n) to store the graph and the resulting path.

Ready to solve this problem?

Practice Valid Arrangement of Pairs with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find if Path Exists in Graph

Next

Reconstruct Itinerary