Valid Arrangement of Pairs solution and explanation
Google
9 more videos on this problem
Hierholzer's Algorithm | Valid Arrangement of Pairs | Leetcode 2097 | Graph Concepts & Qns - 43codestorywithMIK · 31:41 · 17K views
Valid Arrangement of Pairs | Leetcode 2097Techdose · 30:26 · 5K views
2097. Valid Arrangement of Pairs | No Pre-requisite | Eulerian Path | DFSAryan Mittal · 35:13 · 2K views
Leetcode 2097 Valid Arrangement of Pairs. Eulerian path, Graph theory and code.Interview Ready · 28:51 · 1K views
Leetcode 2097 Valid Arrangement of Pairs : Hierholzer's AlgorithmMath Geeks · 5:40 · 1K views
【每日一题】LeetCode 2097. Valid Arrangement of PairsHuifeng Guan · 32:27 · 1K views
Daily Leetcode #1705: Nov 30, 2024 - 2097. Valid Arrangement of PairsProgramming Live with Larry · 1:02:46 · 742 views
LeetCode 2097 Valid Arrangement of Pairs | Eulerian Path Construction | Graph Theory | Meta 🔥Code Harmony · 21:08 · 412 views
Valid Arrangement of Pairs | Leetcode 2097 | Eulerian Path | Graphs | Java Code | Developer CoderDeveloper Coder · 29:39 · 263 views
2097. Valid Arrangement Of Pairs | Leetcode Daily | Super Hard | DSA | Detailed Solution & AnalysisIts Code Time · 30:09 · 219 views
The problem
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 != 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.
The written solution for this problem is still being prepared. Try it yourself in the meantime.
Try solving it yourselfComplexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking / Permutation Search | O(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 Stack | O(n) | O(n) | Preferred when avoiding recursion depth limits |
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.