The “Check Array Formation Through Concatenation” problem on Leetcode is a thought-provoking challenge that requires a good understanding of array manipulation and algorithmic thinking. The problem sits at the intersection of various programming concepts like searching, slicing, and data structure utilization, making it an interesting study.

In this extensive article, we will dissect the problem’s requirements, examine multiple approaches to solve it, delve into their time and space complexity, and implement the solutions in Python.

## Problem Description

The problem statement is as follows:

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 the individual arrays `pieces[i]`

.

Return `True`

if it is possible to form the array `arr`

from `pieces`

. Otherwise, return `False`

.

#### Example

`canFormArray([85, 15, 105], [[105], [15], [85]]) # Output: True`

## Approach 1: Hash Map Lookup

### Algorithm

- Create a hash map (dictionary) from the
`pieces`

array to make lookups efficient. - Iterate through the
`arr`

while looking up the first element of each subarray in`pieces`

. - If found, check the subsequent elements in
`arr`

with those in the found piece and skip them.

### Python Code

```
from typing import List
def canFormArray(arr: List[int], pieces: List[List[int]]) -> bool:
piece_map = {piece[0]: piece for piece in pieces}
i = 0
while i < len(arr):
if arr[i] not in piece_map:
return False
piece = piece_map[arr[i]]
for num in piece:
if i < len(arr) and arr[i] == num:
i += 1
else:
return False
return True
```

### Time Complexity

The time complexity for this approach is O(n), where n is the length of the array `arr`

.

### Space Complexity

The space complexity is O(m), where m is the number of individual `pieces`

.

## Approach 2: String Conversion

### Algorithm

- Convert the
`arr`

and each piece in`pieces`

to strings. - Check if the string of
`arr`

can be formed by the concatenation of strings of`pieces`

.

### Python Code

```
def canFormArray(arr: List[int], pieces: List[List[int]]) -> bool:
arr_str = ''.join(map(str, arr))
pieces_str = ["".join(map(str, piece)) for piece in pieces]
for piece_str in pieces_str:
arr_str = arr_str.replace(piece_str, "")
return not arr_str
```

### Time Complexity

The time complexity is O(n), but with a larger constant factor due to string operations.

### Space Complexity

The space complexity is O(n) due to the storage required for string conversion.

## Conclusion

The “Check Array Formation Through Concatenation” problem on Leetcode allows us to explore interesting algorithms and techniques related to array manipulation. We discussed two different approaches: one using hash map lookups and another using string conversion. Both methods have their merits and trade-offs in terms of time and space complexity.