DSA problem
Valid Arrangement of Pairs
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. The input is guaranteed to admit at least one valid arrangement.
This is an Eulerian path problem in disguise. Treat each pair [u, v] as a directed edge u -> v in a multigraph. A "valid arrangement" is precisely a sequence of edges in which each edge's tail equals the previous edge's head — i.e. an Eulerian path that uses every edge exactly once. Because the input is guaranteed to permit such an arrangement, an Eulerian path is guaranteed to exist in this graph.
The starting vertex matters. If there is some vertex s whose out-degree exceeds its in-degree by exactly one, the Eulerian path must begin at s; otherwise the graph has an Eulerian circuit and we may begin at any vertex with at least one outgoing edge (an arbitrary vertex from the first pair works). After fixing the start, the rest of the construction is Hierholzer's algorithm.
The optimal approach builds an adjacency map from u to a stack of outgoing destinations, computes in- and out-degrees, picks the correct start, and runs an iterative DFS that consumes edges and emits them in reverse post-order. Each emitted edge corresponds to a pair, so reversing the emission list yields a valid arrangement. The algorithm runs in O(V + E) time and space, where E = pairs.length.
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]]Constraints
- 1 <= pairs.length <= 10^5
- pairs[i].length == 2
- 0 <= starti, endi <= 10^9
- The input is guaranteed to have a valid arrangement.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.