Valid Arrangement of Pairs
Asked at Goldman Sachs
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.
Asked At
| 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).
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
from 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.