2097. Valid Arrangement of Pairs
Asked at Goldman Sachs
Difficulty
Hard
Time
O(E)
Space
O(E)
Pattern
Depth-First Search
Companies
1
Problem
You are given a list of pairs, where each pair is [start, end]. You must reorder the pairs so that they chain together: the end of one pair must equal the start of the next pair. Return any valid ordering.
Think of each pair as a directed edge from start to end. A valid arrangement is a path that uses every edge exactly once. This is called an Eulerian path. The input is guaranteed to have at least one valid arrangement.
You do not need to find the only answer — any correct ordering is accepted. The numbers can be large (up to 10^9), so use a hash map for the graph, not an array.
Chain the pairs end to start
Constraints
- ●
1 <= pairs.length <= 10^5 - ●
pairs[i].length == 2 - ●
0 <= start_i, end_i <= 10^9 - ●
start_i != end_i - ●
No two pairs are exactly the same - ●
There exists a valid arrangement of pairs
Examples
pairs = [[5,1],[4,5],[11,9],[9,4]][[11,9],[9,4],[4,5],[5,1]]pairs = [[1,3],[3,2],[2,1]][[1,3],[3,2],[2,1]]pairs = [[1,2],[1,3],[2,1]][[1,2],[2,1],[1,3]]Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Goldman Sachs | Hard | View all Goldman Sachs questions → |
How to Think About It
Model numbers as nodes and each pair as a directed edge start -> end. A valid arrangement is a path using every edge exactly once — an Eulerian path.
Where to start: if some node has out-degree - in-degree = 1, the path must start there. Otherwise every node is balanced (an Eulerian circuit), so start anywhere with outgoing edges.
Key insight (Hierholzer): walk edges greedily, removing each as you use it. When you reach a node with no unused edges, add it to the output and back up. The output, reversed, is the Eulerian path — detours get spliced in automatically.
Use an explicit stack instead of recursion; there can be 10^5 edges.
Convert the node sequence back into pairs: consecutive nodes (path[i], path[i+1]).
Optimal Approach
Step 1: Build adjacency lists and out - in degree differences.
Step 2: start = node with difference 1, or pairs[0][0] if none.
Step 3: Stack-based Hierholzer: push start; while the stack is not empty, if the top has unused edges, pop one edge and push its target; otherwise pop the top into path.
Step 4: Reverse path and return [[path[i], path[i+1]] ...].
Time: O(E). Space: O(E).
Hierholzer walks edges and backtracks
What Trips People Up in Real Interviews
Trying backtracking over pair orders — exponential.
Starting at an arbitrary node when a node with extra out-degree exists; the walk then gets stuck with unused edges.
Appending nodes to the path when you enter them instead of when you leave them. Hierholzer's post-order is what splices detours correctly.
Recursing 10^5 deep in Python or Java. Use an explicit stack.
Solution Code
O(E) timefrom collections import defaultdict
def validArrangement(pairs):
adj = defaultdict(list)
diff = defaultdict(int)
for a, b in pairs:
adj[a].append(b)
diff[a] += 1
diff[b] -= 1
start = pairs[0][0]
for node, d in diff.items():
if d == 1:
start = node
break
stack = [start]
path = []
while stack:
u = stack[-1]
if adj[u]:
stack.append(adj[u].pop())
else:
path.append(stack.pop())
path.reverse()
return [[path[i], path[i + 1]] for i in range(len(path) - 1)]Frequently Asked Questions
What is the Valid Arrangement of Pairs problem?
Valid Arrangement of Pairs asks you to reorder pairs `[start, end]` so that each pair's end equals the next pair's start. Treat each pair as a directed edge — you need a path that uses every edge exactly once, which is an Eulerian path. Hierholzer's algorithm builds it in linear time.
How do you solve Valid Arrangement of Pairs?
The optimal approach runs in O(E) time and O(E) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Valid Arrangement of Pairs?
Valid Arrangement of Pairs is asked at Goldman Sachs. It is a hard difficulty problem.
What are common mistakes on Valid Arrangement of Pairs?
- Trying backtracking over pair orders — exponential.
- Starting at an arbitrary node when a node with extra out-degree exists; the walk then gets stuck with unused edges.
- Appending nodes to the path when you enter them instead of when you leave them. Hierholzer's post-order is what splices detours correctly.
- Recursing `10^5` deep in Python or Java. Use an explicit stack.