1072. Chain the Pairs
A craft shop sells wooden rail segments. Every segment has a numbered coupler on each end, and two segments can be joined only where the touching couplers carry the same number. A segment may be turned around, so the segment [a, b] can be laid as a → b or as b → a.
Given the list pairs, lay out every segment exactly once in a single line so that the second number of each segment equals the first number of the segment after it. Return the line as a list of segments, each written in the orientation in which it is laid. If no such line exists, return an empty list.
Any valid line is accepted. Segments may repeat, and a segment may carry the same number on both ends.
Example 1
- Input:
- pairs = [[3,8],[8,5],[1,3]]
- Output:
- [[1,3],[3,8],[8,5]]
- Explanation:
The numbers 1, 3, 8, 5 form one path through the three pairs, so a chain exists (it may be read in either direction).
Example 2
- Input:
- pairs = [[1,2],[3,4]]
- Output:
- []
- Explanation:
Neither number of
[1, 2]appears in[3, 4], so the two pairs can never touch and the answer is empty.
Example 3
- Input:
- pairs = [[4,6],[6,4],[4,4]]
- Output:
- [[4,6],[6,4],[4,4]]
- Explanation:
Lay 4→6, then 6→4, then the loop 4→4; every pair is used once.
Constraints
1 ≤ pairs.length ≤ 105
pairs[i].length == 2
0 ≤ pairs[i][j] ≤ 105
How this problem is judged
- Answers
- Any valid answer is accepted. A checker tests yours against the problem's rules.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(V + E)
- Space
- O(V + E)