Uber | CodeSignal OA | Construct an array by concatenating given smaller arrays
Anonymous User
2310

You are given an array A containing distinct integers and a bunch of smaller arrays called pieces[][]. Check whether we could concatenate these smaller arrays in pieces[][] to construct A. You must use all the elements from pieces[i] and you cannot change the order of elements in pieces[i].

Examples

1. A = [1, 2, 5, 3]
pieces = [[3], [1, 2], [5]]
return true

2. A = [1, 2, 5, 3] 
pieces = [3, [2, 1], [5]]
return false

3. A = [1, 2, 5, 3]
pieces = [[1,3], [2, 5]]
return false;

My solution - create a LinkedList from A, for every piece i in pieces delete its elements from A. If at any point there is a mismatch between pieces[i][j] and A[k], return false. If at the end A is non-empty return false or else return true. This solution TLE'd for 2 test cases.

Alternative (did not get to code it) - do not delete elements from the list, instead simply match the elements in A and given pieces. If number of elements matched != size of A, return false.

Can anyone please let me know if there is a better solution?

Comments (11)