Array
Hash Table
Description
You are given an array of distinct integers arr
and an array of integer arrays pieces
, where the integers in pieces
are distinct . Your goal is to form arr
by concatenating the arrays in pieces
in any order . However, you are not allowed to reorder the integers in each array pieces[i]
.
Return true
if it is possible to form the array arr
from pieces
. Otherwise, return false
.
Example 1:
Input: arr = [15,88], pieces = [[88],[15]]
Output: true
Explanation: Concatenate [15] then [88]
Example 2:
Input: arr = [49,18,16], pieces = [[16,18,49]]
Output: false
Explanation: Even though the numbers match, we cannot reorder pieces[0].
Example 3:
Input: arr = [91,4,64,78], pieces = [[78],[4,64],[91]]
Output: true
Explanation: Concatenate [91] then [4,64] then [78]
Constraints:
1 <= pieces.length <= arr.length <= 100
sum(pieces[i].length) == arr.length
1 <= pieces[i].length <= arr.length
1 <= arr[i], pieces[i][j] <= 100
The integers in arr
are distinct .
The integers in pieces
are distinct (i.e., If we flatten pieces in a 1D array, all the integers in this array are distinct).
Solutions
Solution 1
Python3 Java C++ Go TypeScript Rust JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13 class Solution :
def canFormArray ( self , arr : List [ int ], pieces : List [ List [ int ]]) -> bool :
i = 0
while i < len ( arr ):
k = 0
while k < len ( pieces ) and pieces [ k ][ 0 ] != arr [ i ]:
k += 1
if k == len ( pieces ):
return False
j = 0
while j < len ( pieces [ k ]) and arr [ i ] == pieces [ k ][ j ]:
i , j = i + 1 , j + 1
return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 class Solution {
public boolean canFormArray ( int [] arr , int [][] pieces ) {
for ( int i = 0 ; i < arr . length ;) {
int k = 0 ;
while ( k < pieces . length && pieces [ k ][ 0 ] != arr [ i ] ) {
++ k ;
}
if ( k == pieces . length ) {
return false ;
}
int j = 0 ;
while ( j < pieces [ k ] . length && arr [ i ] == pieces [ k ][ j ] ) {
++ i ;
++ j ;
}
}
return true ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 class Solution {
public :
bool canFormArray ( vector < int >& arr , vector < vector < int >>& pieces ) {
for ( int i = 0 ; i < arr . size ();) {
int k = 0 ;
while ( k < pieces . size () && pieces [ k ][ 0 ] != arr [ i ]) {
++ k ;
}
if ( k == pieces . size ()) {
return false ;
}
int j = 0 ;
while ( j < pieces [ k ]. size () && arr [ i ] == pieces [ k ][ j ]) {
++ i ;
++ j ;
}
}
return true ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 func canFormArray ( arr [] int , pieces [][] int ) bool {
for i := 0 ; i < len ( arr ); {
k := 0
for k < len ( pieces ) && pieces [ k ][ 0 ] != arr [ i ] {
k ++
}
if k == len ( pieces ) {
return false
}
j := 0
for j < len ( pieces [ k ]) && arr [ i ] == pieces [ k ][ j ] {
i , j = i + 1 , j + 1
}
}
return true
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 function canFormArray ( arr : number [], pieces : number [][]) : boolean {
const n = arr . length ;
let i = 0 ;
while ( i < n ) {
const target = arr [ i ];
const items = pieces . find ( v => v [ 0 ] === target );
if ( items == null ) {
return false ;
}
for ( const item of items ) {
if ( item !== arr [ i ]) {
return false ;
}
i ++ ;
}
}
return true ;
}
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 use std :: collections :: HashMap ;
impl Solution {
pub fn can_form_array ( arr : Vec < i32 > , pieces : Vec < Vec < i32 >> ) -> bool {
let n = arr . len ();
let mut map = HashMap :: new ();
for ( i , v ) in pieces . iter (). enumerate () {
map . insert ( v [ 0 ], i );
}
let mut i = 0 ;
while i < n {
match map . get ( & arr [ i ]) {
None => {
return false ;
}
Some ( & j ) => {
for & item in pieces [ j ]. iter () {
if item != arr [ i ] {
return false ;
}
i += 1 ;
}
}
}
}
true
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 /**
* @param {number[]} arr
* @param {number[][]} pieces
* @return {boolean}
*/
var canFormArray = function ( arr , pieces ) {
const d = new Map ();
for ( const p of pieces ) {
d . set ( p [ 0 ], p );
}
for ( let i = 0 ; i < arr . length ; ) {
if ( ! d . has ( arr [ i ])) {
return false ;
}
const p = d . get ( arr [ i ]);
for ( const v of p ) {
if ( arr [ i ++ ] != v ) {
return false ;
}
}
}
return true ;
};
Solution 2
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12 class Solution :
def canFormArray ( self , arr : List [ int ], pieces : List [ List [ int ]]) -> bool :
d = { p [ 0 ]: p for p in pieces }
i , n = 0 , len ( arr )
while i < n :
if arr [ i ] not in d :
return False
p = d [ arr [ i ]]
if arr [ i : i + len ( p )] != p :
return False
i += len ( p )
return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 class Solution {
public boolean canFormArray ( int [] arr , int [][] pieces ) {
Map < Integer , int []> d = new HashMap <> ();
for ( var p : pieces ) {
d . put ( p [ 0 ] , p );
}
for ( int i = 0 ; i < arr . length ;) {
if ( ! d . containsKey ( arr [ i ] )) {
return false ;
}
for ( int v : d . get ( arr [ i ] )) {
if ( arr [ i ++] != v ) {
return false ;
}
}
}
return true ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 class Solution {
public :
bool canFormArray ( vector < int >& arr , vector < vector < int >>& pieces ) {
unordered_map < int , vector < int >> d ;
for ( auto & p : pieces ) {
d [ p [ 0 ]] = p ;
}
for ( int i = 0 ; i < arr . size ();) {
if ( ! d . count ( arr [ i ])) {
return false ;
}
for ( int & v : d [ arr [ i ]]) {
if ( arr [ i ++ ] != v ) {
return false ;
}
}
}
return true ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 func canFormArray ( arr [] int , pieces [][] int ) bool {
d := map [ int ][] int {}
for _ , p := range pieces {
d [ p [ 0 ]] = p
}
for i := 0 ; i < len ( arr ); {
p , ok := d [ arr [ i ]]
if ! ok {
return false
}
for _ , v := range p {
if arr [ i ] != v {
return false
}
i ++
}
}
return true
}