Valid Arrangement of Pairs

arraydepth-first searchgraph theory

Problem Statement

You are given a 0-indexed 2D integer array pairs where pairs[i] = [start _i , end _i ] . An arrangement of pairs is valid if for every index i where 1 <= i < pairs.length , we have end _i-1 == start _i .

Return any valid arrangement of pairs .

Note: The inputs will be generated such that there exists a valid arrangement of pairs .

Examples

Example 1

Input: pairs = [[5,1],[4,5],[11,9],[9,4]]
Output: [[11,9],[9,4],[4,5],[5,1]]
This is a valid arrangement since end _i-1 always equals start _i .
end _0 = 9 == 9 = start _1 
end _1 = 4 == 4 = start _2 
end _2 = 5 == 5 = start _3

Example 2

Input: pairs = [[1,3],[3,2],[2,1]]
Output: [[1,3],[3,2],[2,1]]
This is a valid arrangement since end _i-1 always equals start _i .
end _0 = 3 == 3 = start _1 
end _1 = 2 == 2 = start _2 
The arrangements [[2,1],[1,3],[3,2]] and [[3,2],[2,1],[1,3]] are also valid.

Example 3

Input: pairs = [[1,2],[1,3],[2,1]]
Output: [[1,2],[2,1],[1,3]]
This is a valid arrangement since end _i-1 always equals start _i .
end _0 = 2 == 2 = start _1 
end _1 = 1 == 1 = start _2

Constraints

1 <= pairs.length <= 10 ^5

pairs[i].length == 2

0 <= start _i , end _i <= 10 ^9

start _i != end _i

No two pairs are exactly the same.

There exists a valid arrangement of pairs .

😤

Hard

Difficulty

Topic Info

ModuleDSA

CategoryArray

Sub-topicDepth-First Search