AlgoMaster Logo

Valid Arrangement of Pairs

hardFrequencyUpdated September 21, 2026

Understanding the Problem

This reads like a sequencing problem: arrange the pairs so that consecutive pairs chain together, where the end of one matches the start of the next. The reframing that makes it tractable is to treat each pair [start, end] as a directed edge from node start to node end. Then the task is to find a path that uses every edge exactly once.

That is the definition of an Eulerian path: a path that traverses every edge in a graph exactly once. If the path ends where it starts, it is an Eulerian circuit. The problem guarantees a valid arrangement exists, so the graph formed by these pairs has an Eulerian path or circuit.

Two questions remain: which node do we start from, and how do we build the path efficiently once we know the start?

Key Constraints:

  • 1 <= pairs.length <= 10^5 --> With up to 100,000 edges, we need an algorithm that is roughly O(E) where E is the number of edges. Anything O(E^2) would be too slow.
  • 0 <= start_i, end_i <= 10^9 --> Node values can be very large, so we need to use a hash map (not an array) for the adjacency list.
  • The problem guarantees a valid arrangement exists, so the graph is guaranteed to have an Eulerian path or circuit.

Approach 1: Brute Force (Backtracking)

Intuition

Try all possible orderings of the pairs and check whether any forms a valid chain. A pair can go next in the sequence only if its start matches the end of the previous pair, so the search is a backtracking walk: at each position, place an unused pair that connects to the last one, recurse to build the rest, and undo the choice if it leads to a dead end.

Algorithm

  1. Start by trying each pair as the first element.
  2. For each subsequent position, find a pair whose start matches the end of the last placed pair.
  3. Mark pairs as used to avoid reuse.
  4. If all pairs are placed, return the arrangement.
  5. If stuck, backtrack and try a different pair.

Visualization and Code

Loading animation...

The factorial search space makes this approach unusable past a handful of pairs. Modeling the pairs as a directed graph turns the problem into finding a path that visits every edge once, which has a linear-time algorithm.

Approach 2: Hierholzer's Algorithm (Eulerian Path)

Intuition

With the pairs as directed edges, finding an arrangement is finding an Eulerian path. Hierholzer's algorithm finds one in directed graphs in O(E) time.

The mechanism: start from the correct node, then follow unused edges greedily. When the current node has no more unused edges, the walk has closed a sub-circuit, so record that node and step back to its predecessor. The nodes recorded at these dead ends, read in reverse, form the Eulerian path.

In a directed graph, an Eulerian path exists if and only if:

  • At most one node has out-degree - in-degree = 1 (this is the start node)
  • At most one node has in-degree - out-degree = 1 (this is the end node)
  • All other nodes have equal in-degree and out-degree

If every node has equal in-degree and out-degree, it is an Eulerian circuit and we can start from any node. Otherwise, we must start from the node where out-degree exceeds in-degree by 1.

Algorithm

  1. Build an adjacency list from the pairs. Each pair [start, end] adds end to the neighbor list of start.
  2. Track in-degree and out-degree for each node using a single degree map where out-degree contributes +1 and in-degree contributes -1.
  3. Find the start node: the node where the net degree equals +1. If no such node exists, pick any node (it is a circuit).
  4. Run Hierholzer's algorithm: use a stack-based DFS. Pop an edge from the current node's adjacency list, move to the next node. When a node has no more edges, add it to the path and backtrack.
  5. Reverse the collected path to get the correct order.
  6. Convert the node path back into pairs: each consecutive pair of nodes [path[i], path[i+1]] forms one result pair.

Visualization and Code

Loading animation...