Valid Arrangement of Pairs
Real-world version: Chaining Every Run in the YardThe statement here is our own: the same inputs, outputs and technique.
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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def valid_arrangement(pairs: list[list[int]]) -> list[list[int]]:public int[][] validArrangement(int[][] pairs)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 10 test cases: 10 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's