Domino Chain Order
HardAdvanced Graphs
Problem
You have a set of directed dominoes. Each pieces[i] = [a, b] can only be laid as a → b, and the next domino must start with the number the previous one ended with. All pieces must be used exactly once.
Return the chain as the sequence of numbers it passes through (length pieces.length + 1). If several chains exist, return the lexicographically smallest sequence, comparing number by number. If no chain uses every piece, return [].
Example 1
- Input:
- pieces = [[3,1],[1,2],[2,3],[3,4]]
- Output:
- [3, 1, 2, 3, 4]
3 has one more outgoing piece than incoming ones, so the chain must start there; 4 must be last.
Example 2
- Input:
- pieces = [[1,2],[2,1]]
- Output:
- [1, 2, 1]
A loop may start anywhere; starting at 1 is smallest.
Example 3
- Input:
- pieces = [[1,2],[3,4]]
- Output:
- []
The two pieces cannot be joined.
Constraints
- 1 ≤ pieces.length ≤ 10^4
- 0 ≤ a, b ≤ 10^5
- a = b is allowed (a self-loop).
Hint
Show the first hint
Numbers are vertices and pieces are directed edges: you need an Eulerian path.
Walkthrough
How to approach it
01Clarify before coding
- Is the start given? No: it is forced by the degrees, or free if every number is balanced.
- Do pieces flip? No, a → b only.
- What if the pieces form two separate loops? No chain exists: return [].
02Brute force
Backtrack from every possible start, trying the smallest next piece first, and return the first full chain.
Cost: Exponential in the worst case, since wrong branches may consume many pieces before failing.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.