> For the complete documentation index, see [llms.txt](https://txfs19260817.gitbook.io/leetcode-go-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://txfs19260817.gitbook.io/leetcode-go-notes/solutions/1640.-check-array-formation-through-concatenation.md).

# 1640. Check Array Formation Through Concatenation

## LeetCode [1640. Check Array Formation Through Concatenation](https://github.com/txfs19260817/LeetCode-Go/blob/master/solutions/title/README.md)

### 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].
```

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

### Tags

Array, Hash Table, Sort

### Solution

Employ a hash table to index pieces using the first character of each piece as the key to speedup lookup. Then, we use each character in `arr` to query a piece and join them together to obtain a new array. Return the result that if `arr` and the new array are the same.

### Complexity

* Time complexity: $$O(n)$$, `n` for the length of `arr`;
* Space complexity: $$O(m)$$, `m` for the length of `pieces`.

### Code

```go
func canFormArray(arr []int, pieces [][]int) bool {
	connected, dict := make([]int, 0, len(arr)), map[int][]int{} // pieces[i][0]:pieces[i]
	for _, piece := range pieces {
		dict[piece[0]] = piece
	}
	for _, a := range arr {
		connected = append(connected, dict[a]...)
	}
	if len(arr) != len(connected) {
		return false
	}
	for i := 0; i < len(arr); i++ {
		if arr[i] != connected[i] {
			return false
		}
	}
	return true
}
```

## Reference