Depth-First Search
Array
Hash Table
Description
There is an integer array nums
that consists of n
unique elements, but you have forgotten it. However, you do remember every pair of adjacent elements in nums
.
You are given a 2D integer array adjacentPairs
of size n - 1
where each adjacentPairs[i] = [ui , vi ]
indicates that the elements ui
and vi
are adjacent in nums
.
It is guaranteed that every adjacent pair of elements nums[i]
and nums[i+1]
will exist in adjacentPairs
, either as [nums[i], nums[i+1]]
or [nums[i+1], nums[i]]
. The pairs can appear in any order .
Return the original array nums
. If there are multiple solutions, return any of them .
Example 1:
Input: adjacentPairs = [[2,1],[3,4],[3,2]]
Output: [1,2,3,4]
Explanation: This array has all its adjacent pairs in adjacentPairs.
Notice that adjacentPairs[i] may not be in left-to-right order.
Example 2:
Input: adjacentPairs = [[4,-2],[1,4],[-3,1]]
Output: [-2,4,1,-3]
Explanation: There can be negative numbers.
Another solution is [-3,1,4,-2], which would also be accepted.
Example 3:
Input: adjacentPairs = [[100000,-100000]]
Output: [100000,-100000]
Constraints:
nums.length == n
adjacentPairs.length == n - 1
adjacentPairs[i].length == 2
2 <= n <= 105
-105 <= nums[i], ui , vi <= 105
There exists some nums
that has adjacentPairs
as its pairs.
Solutions
Solution 1
Python3 Java C++ Go C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 class Solution :
def restoreArray ( self , adjacentPairs : List [ List [ int ]]) -> List [ int ]:
g = defaultdict ( list )
for a , b in adjacentPairs :
g [ a ] . append ( b )
g [ b ] . append ( a )
n = len ( adjacentPairs ) + 1
ans = [ 0 ] * n
for i , v in g . items ():
if len ( v ) == 1 :
ans [ 0 ] = i
ans [ 1 ] = v [ 0 ]
break
for i in range ( 2 , n ):
v = g [ ans [ i - 1 ]]
ans [ i ] = v [ 0 ] if v [ 1 ] == ans [ i - 2 ] else v [ 1 ]
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 class Solution {
public int [] restoreArray ( int [][] adjacentPairs ) {
int n = adjacentPairs . length + 1 ;
Map < Integer , List < Integer >> g = new HashMap <> ();
for ( int [] e : adjacentPairs ) {
int a = e [ 0 ] , b = e [ 1 ] ;
g . computeIfAbsent ( a , k -> new ArrayList <> ()). add ( b );
g . computeIfAbsent ( b , k -> new ArrayList <> ()). add ( a );
}
int [] ans = new int [ n ] ;
for ( Map . Entry < Integer , List < Integer >> entry : g . entrySet ()) {
if ( entry . getValue (). size () == 1 ) {
ans [ 0 ] = entry . getKey ();
ans [ 1 ] = entry . getValue (). get ( 0 );
break ;
}
}
for ( int i = 2 ; i < n ; ++ i ) {
List < Integer > v = g . get ( ans [ i - 1 ] );
ans [ i ] = v . get ( 1 ) == ans [ i - 2 ] ? v . get ( 0 ) : v . get ( 1 );
}
return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 class Solution {
public :
vector < int > restoreArray ( vector < vector < int >>& adjacentPairs ) {
int n = adjacentPairs . size () + 1 ;
unordered_map < int , vector < int >> g ;
for ( auto & e : adjacentPairs ) {
int a = e [ 0 ], b = e [ 1 ];
g [ a ]. push_back ( b );
g [ b ]. push_back ( a );
}
vector < int > ans ( n );
for ( auto & [ k , v ] : g ) {
if ( v . size () == 1 ) {
ans [ 0 ] = k ;
ans [ 1 ] = v [ 0 ];
break ;
}
}
for ( int i = 2 ; i < n ; ++ i ) {
auto v = g [ ans [ i - 1 ]];
ans [ i ] = v [ 0 ] == ans [ i - 2 ] ? v [ 1 ] : v [ 0 ];
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 func restoreArray ( adjacentPairs [][] int ) [] int {
n := len ( adjacentPairs ) + 1
g := map [ int ][] int {}
for _ , e := range adjacentPairs {
a , b := e [ 0 ], e [ 1 ]
g [ a ] = append ( g [ a ], b )
g [ b ] = append ( g [ b ], a )
}
ans := make ([] int , n )
for k , v := range g {
if len ( v ) == 1 {
ans [ 0 ] = k
ans [ 1 ] = v [ 0 ]
break
}
}
for i := 2 ; i < n ; i ++ {
v := g [ ans [ i - 1 ]]
ans [ i ] = v [ 0 ]
if v [ 0 ] == ans [ i - 2 ] {
ans [ i ] = v [ 1 ]
}
}
return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 public class Solution {
public int [] RestoreArray ( int [][] adjacentPairs ) {
int n = adjacentPairs . Length + 1 ;
Dictionary < int , List < int >> g = new Dictionary < int , List < int >> ();
foreach ( int [] e in adjacentPairs ) {
int a = e [ 0 ], b = e [ 1 ];
if ( ! g . ContainsKey ( a )) {
g [ a ] = new List < int > ();
}
if ( ! g . ContainsKey ( b )) {
g [ b ] = new List < int > ();
}
g [ a ]. Add ( b );
g [ b ]. Add ( a );
}
int [] ans = new int [ n ];
foreach ( var entry in g ) {
if ( entry . Value . Count == 1 ) {
ans [ 0 ] = entry . Key ;
ans [ 1 ] = entry . Value [ 0 ];
break ;
}
}
for ( int i = 2 ; i < n ; ++ i ) {
List < int > v = g [ ans [ i - 1 ]];
ans [ i ] = v [ 1 ] == ans [ i - 2 ] ? v [ 0 ] : v [ 1 ];
}
return ans ;
}
}
Solution 2
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 class Solution :
def restoreArray ( self , adjacentPairs : List [ List [ int ]]) -> List [ int ]:
def dfs ( i , fa ):
ans . append ( i )
for j in g [ i ]:
if j != fa :
dfs ( j , i )
g = defaultdict ( list )
for a , b in adjacentPairs :
g [ a ] . append ( b )
g [ b ] . append ( a )
i = next ( i for i , v in g . items () if len ( v ) == 1 )
ans = []
dfs ( i , 1e6 )
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 class Solution {
private Map < Integer , List < Integer >> g = new HashMap <> ();
private int [] ans ;
public int [] restoreArray ( int [][] adjacentPairs ) {
for ( var e : adjacentPairs ) {
int a = e [ 0 ] , b = e [ 1 ] ;
g . computeIfAbsent ( a , k -> new ArrayList <> ()). add ( b );
g . computeIfAbsent ( b , k -> new ArrayList <> ()). add ( a );
}
int n = adjacentPairs . length + 1 ;
ans = new int [ n ] ;
for ( var e : g . entrySet ()) {
if ( e . getValue (). size () == 1 ) {
dfs ( e . getKey (), 1000000 , 0 );
break ;
}
}
return ans ;
}
private void dfs ( int i , int fa , int k ) {
ans [ k ++] = i ;
for ( int j : g . get ( i )) {
if ( j != fa ) {
dfs ( j , i , k );
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 class Solution {
public :
vector < int > restoreArray ( vector < vector < int >>& adjacentPairs ) {
unordered_map < int , vector < int >> g ;
for ( auto & e : adjacentPairs ) {
int a = e [ 0 ], b = e [ 1 ];
g [ a ]. emplace_back ( b );
g [ b ]. emplace_back ( a );
}
int n = adjacentPairs . size () + 1 ;
vector < int > ans ;
function < void ( int , int ) > dfs = [ & ]( int i , int fa ) {
ans . emplace_back ( i );
for ( int & j : g [ i ]) {
if ( j != fa ) {
dfs ( j , i );
}
}
};
for ( auto & [ i , v ] : g ) {
if ( v . size () == 1 ) {
dfs ( i , 1e6 );
break ;
}
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 func restoreArray ( adjacentPairs [][] int ) [] int {
g := map [ int ][] int {}
for _ , e := range adjacentPairs {
a , b := e [ 0 ], e [ 1 ]
g [ a ] = append ( g [ a ], b )
g [ b ] = append ( g [ b ], a )
}
ans := [] int {}
var dfs func ( i , fa int )
dfs = func ( i , fa int ) {
ans = append ( ans , i )
for _ , j := range g [ i ] {
if j != fa {
dfs ( j , i )
}
}
}
for i , v := range g {
if len ( v ) == 1 {
dfs ( i , 1000000 )
break
}
}
return ans
}