0892HardArrayDepth-First SearchGraph TheoryEulerian CircuitEulerian PathSemi-Eulerian Graph

Chaining Every Run in the Yard

Tracked in this browser only

Trains the technique from

LeetCode 2097Valid Arrangement of Pairs

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A haulage log is given as pairs, where pairs[i] is [from, to] for one run between two junctions. The two junctions on a run are never the same, and no run is logged twice.

An itinerary puts every run in some order so that each run starts where the one before it ended. At least one itinerary is guaranteed to exist.

Write an itinerary out flat, as the junctions of its first run followed by those of its second, and so on. Return the itinerary whose flat form comes first in dictionary order.

Examples

Example 1

Input: pairs = [[0, 1], [0, 2], [2, 0], [1, 3]]
Output: [[0, 2], [2, 0], [0, 1], [1, 3]]

Junction 0 has one more departure than arrival, so the itinerary has to open there, and junction 3 has one more arrival, so it closes there. Setting off on the run to junction 1 would strand the pair between 0 and 2, so the itinerary goes 0 to 2, back to 0, on to 1 and then to 3.

Example 2

Input: pairs = [[3, 1], [1, 2], [2, 3]]
Output: [[1, 2], [2, 3], [3, 1]]

Every junction balances, so the itinerary closes where it opened and may open anywhere on the loop. Opening at junction 1 gives the smallest flat form.

Example 3

Input: pairs = [[5, 8]]
Output: [[5, 8]]

A single run is already an itinerary.

Constraints

1 <= pairs.length <= 200
pairs[i].length == 2
0 <= pairs[i][0] <= 10^9
0 <= pairs[i][1] <= 10^9
The two junctions on a run are different
No run is logged twice
At least one itinerary exists

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def valid_arrangement(pairs: list[list[int]]) -> list[list[int]]:

Java

public int[][] validArrangement(int[][] pairs)

The intended approach

Time O(e^2 * d) for e runs and a largest junction out-count of d: each of the e steps tries up to d runs, and each trial sweeps the unused runs once.Space O(e) for the run lists and the used flags.

An itinerary is a walk that uses every run exactly once, so the log admits one only when the junction counts line up: leaving and arriving must balance at every junction bar at most two, one with a spare departure that has to be the opening junction and one with a spare arrival that has to be the closing one; and every run must be reachable by following runs from the opening junction. Those two facts together are exactly the test for whether a set of runs can still be chained from a given junction, and checking them is one sweep over the unused runs. The dictionary-order demand then settles the choices one at a time. The opening junction is the smallest one from which the whole log can still be chained. From there, at each step try the unused runs leaving the current junction in order of where they end, provisionally take the smallest, and keep it only if the rest can still be chained from the junction it reaches. That look-ahead is what stops the walk from stranding runs behind it, which a plain smallest-first walk does.

Pythonentry point: valid_arrangement

def valid_arrangement(pairs):
    n = len(pairs)
    leaving = {}
    for idx in range(n):
        u, v = pairs[idx]
        leaving.setdefault(u, []).append((v, idx))
    for u in leaving:
        leaving[u].sort()
    used = [False] * n

    def chainable(start, left):
        if left == 0:
            return True
        out_count = {}
        in_count = {}
        for i in range(n):
            if used[i]:
                continue
            u, v = pairs[i]
            out_count[u] = out_count.get(u, 0) + 1
            in_count[v] = in_count.get(v, 0) + 1
        if out_count.get(start, 0) == 0:
            return False
        spare_out = 0
        spare_in = 0
        for x in set(out_count) | set(in_count):
            gap = out_count.get(x, 0) - in_count.get(x, 0)
            if gap > 1 or gap < -1:
                return False
            if gap == 1:
                if x != start:
                    return False
                spare_out += 1
            elif gap == -1:
                spare_in += 1
        if spare_out != spare_in or spare_out > 1:
            return False
        # every unused run has to sit on a walk out of start
        seen = {start}
        stack = [start]
        reached = 0
        while stack:
            u = stack.pop()
            for v, i in leaving.get(u, ()):
                if used[i]:
                    continue
                reached += 1
                if v not in seen:
                    seen.add(v)
                    stack.append(v)
        return reached == left

    opening = None
    for s in sorted(leaving):
        if chainable(s, n):
            opening = s
            break
    order = []
    here = opening
    left = n
    while left > 0:
        for v, i in leaving.get(here, ()):
            if used[i]:
                continue
            used[i] = True
            if chainable(v, left - 1):
                order.append([here, v])
                here = v
                left -= 1
                break
            used[i] = False
    return order

The obvious version

Try every order of the runs, keep the orders where each run starts where the previous one ended, write each of those out flat, and take the smallest. Factorial in the run count and it makes no argument about junction counts or reachability.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_valid_arrangement(pairs):
    import itertools
    n = len(pairs)
    best = None
    for order in itertools.permutations(range(n)):
        ok = True
        for k in range(1, n):
            if pairs[order[k - 1]][1] != pairs[order[k]][0]:
                ok = False
                break
        if not ok:
            continue
        flat = []
        for k in order:
            flat.append(pairs[k][0])
            flat.append(pairs[k][1])
        if best is None or flat < best:
            best = flat
    out = []
    for i in range(0, len(best), 2):
        out.append([best[i], best[i + 1]])
    return out

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in