Valid Arrangement of Pairs
Problem
You are given pairs pairs[i] = [starti, endi]. An arrangement is valid if for every i ≥ 1 we have endi-1 == starti — that is, each pair's start matches the previous pair's end. Return any valid arrangement (one is guaranteed to exist).
Treat each pair as a directed edge start → end and each number as a node. A valid arrangement is then a single walk that uses every edge exactly once — an Eulerian path of the graph.
pairs = [[5,1],[4,5],[11,9],[9,4]][[11,9],[9,4],[4,5],[5,1]]def validArrangement(pairs):
graph = defaultdict(deque) # node -> outgoing neighbors
outdeg, indeg = Counter(), Counter()
for u, v in pairs: # build the directed graph
graph[u].append(v)
outdeg[u] += 1
indeg[v] += 1
start = pairs[0][0] # default start
for node in graph: # Euler path start: out - in == 1
if outdeg[node] - indeg[node] == 1:
start = node
break
stack, circuit = [start], [] # Hierholzer's algorithm
while stack:
node = stack[-1]
if graph[node]: # still have an unused edge
stack.append(graph[node].popleft())
else: # dead end: retreat, record node
circuit.append(stack.pop())
circuit.reverse() # path was built backwards
return [[circuit[i], circuit[i + 1]]
for i in range(len(circuit) - 1)]function validArrangement(pairs) {
const graph = new Map(); // node -> array of neighbors
const out = new Map(), ind = new Map();
const inc = (m, k) => m.set(k, (m.get(k) || 0) + 1);
for (const [u, v] of pairs) { // build the directed graph
if (!graph.has(u)) graph.set(u, []);
graph.get(u).push(v);
inc(out, u); inc(ind, v);
}
let start = pairs[0][0]; // default start
for (const node of graph.keys()) // Euler start: out - in == 1
if ((out.get(node) || 0) - (ind.get(node) || 0) === 1) { start = node; break; }
const stack = [start], circuit = [], idx = new Map(); // Hierholzer
while (stack.length) {
const node = stack[stack.length - 1];
const adj = graph.get(node) || [];
const i = idx.get(node) || 0;
if (i < adj.length) { // still have an unused edge
idx.set(node, i + 1);
stack.push(adj[i]);
} else circuit.push(stack.pop()); // dead end: retreat
}
circuit.reverse(); // path was built backwards
const res = [];
for (let i = 0; i + 1 < circuit.length; i++)
res.push([circuit[i], circuit[i + 1]]);
return res;
}int[][] validArrangement(int[][] pairs) {
Map<Integer, Deque<Integer>> graph = new HashMap<>();
Map<Integer, Integer> out = new HashMap<>(), ind = new HashMap<>();
for (int[] p : pairs) { // build the directed graph
graph.computeIfAbsent(p[0], k -> new ArrayDeque<>()).add(p[1]);
out.merge(p[0], 1, Integer::sum);
ind.merge(p[1], 1, Integer::sum);
}
int start = pairs[0][0]; // default start
for (int node : graph.keySet()) // Euler start: out - in == 1
if (out.getOrDefault(node, 0) - ind.getOrDefault(node, 0) == 1) { start = node; break; }
Deque<Integer> stack = new ArrayDeque<>(); // Hierholzer's algorithm
List<Integer> circuit = new ArrayList<>();
stack.push(start);
while (!stack.isEmpty()) {
int node = stack.peek();
Deque<Integer> adj = graph.get(node);
if (adj != null && !adj.isEmpty()) stack.push(adj.poll());
else circuit.add(stack.pop()); // dead end: retreat
}
Collections.reverse(circuit); // path was built backwards
int[][] res = new int[circuit.size() - 1][2];
for (int i = 0; i + 1 < circuit.size(); i++)
res[i] = new int[]{circuit.get(i), circuit.get(i + 1)};
return res;
}vector<vector<int>> validArrangement(vector<vector<int>>& pairs) {
unordered_map<int, vector<int>> graph; // node -> neighbors
unordered_map<int, int> outd, ind, idx;
for (auto& p : pairs) { // build the directed graph
graph[p[0]].push_back(p[1]);
outd[p[0]]++; ind[p[1]]++;
}
int start = pairs[0][0]; // default start
for (auto& kv : graph) // Euler start: out - in == 1
if (outd[kv.first] - ind[kv.first] == 1) { start = kv.first; break; }
vector<int> stk = {start}, circuit; // Hierholzer's algorithm
while (!stk.empty()) {
int node = stk.back();
auto& adj = graph[node];
if (idx[node] < (int)adj.size()) stk.push_back(adj[idx[node]++]);
else { circuit.push_back(node); stk.pop_back(); } // dead end
}
reverse(circuit.begin(), circuit.end()); // path built backwards
vector<vector<int>> res;
for (int i = 0; i + 1 < (int)circuit.size(); i++)
res.push_back({circuit[i], circuit[i + 1]});
return res;
}Explanation
Think of every pair [u, v] as a directed edge from node u to node v. A valid arrangement lines the pairs up so each end joins the next start, which is exactly a walk that traverses every edge once. That is the definition of an Eulerian path, and the problem promises one exists.
Where does the path start? In a graph that has an Eulerian path (but not a closed circuit) exactly one node has one more outgoing edge than incoming — outdeg − indeg == 1. That node is the start. If no such node exists the graph has an Eulerian circuit and we may begin anywhere, so we fall back to the first pair's start.
Hierholzer's algorithm finds the path in linear time. We keep a stack seeded with the start node. While the node on top still has an unused outgoing edge, we follow it (consuming that edge) and push the neighbor. When a node runs out of edges it is a dead end: we pop it and append it to the circuit list. Popping in this order produces the path reversed, so we reverse the list at the end.
Why does retreating give the right answer? When we get stuck, that node must be the current end of the path; nodes get finalized from the tail backwards, and any side loops we entered get spliced in at the exact point they branch off. The result visits every edge exactly once.
Finally we turn the node sequence back into pairs: consecutive nodes circuit[i] → circuit[i+1] rebuild the original edges in valid order.
For [[5,1],[4,5],[11,9],[9,4]], node 11 has outdeg − indeg = 1, so we start there and walk 11→9→4→5→1, giving [[11,9],[9,4],[4,5],[5,1]].