# LeetCode 1640. Check Array Formation Through Concatenation

## Description

https://leetcode.com/problems/check-if-array-is-sorted-and-rotated/

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 = , pieces = []
Output: true
```

Example 2:

```Input: arr = [15,88], pieces = [,]
Output: true
Explanation: Concatenate `` then ``
```

Example 3:

```Input: arr = [49,18,16], pieces = [[16,18,49]]
Output: false
Explanation: Even though the numbers match, we cannot reorder pieces.
```

Example 4:

```Input: arr = [91,4,64,78], pieces = [,[4,64],]
Output: true
Explanation: Concatenate `` then `[4,64]` then `````

Example 5:

```Input: arr = [1,3,5,7], pieces = [[2,4,6,8]]
Output: false
```

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).

## Explanation

Check if piece character is in the original arr set. If piece length greater than 1, additionally check if the order in original arr matches.

## Python Solution

``````class Solution:
def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:
arr_set = set(arr)

for piece in pieces:
for p in piece:
if p not in arr_set:
return False

if len(piece) > 1:
arr_index = arr.index(piece)

for i in range(len(piece)):
if arr_index + i > len(arr) - 1 or arr[arr_index + i] != piece[i]:
return False

return True            ``````
• Time Complexity: O(N).
• Space Complexity: O(N).