Check Array Formation Through Concatenation

To check whether we can form the given array arr by concatenating the arrays in pieces without reordering the integers in each array, we can follow these steps:

Create a dictionary mapping that maps the first element of each piece to its corresponding array.
Iterate through arr, and for each element, check if it exists in mapping. If it does, then check if the subsequent elements in arr match the elements in the corresponding piece. If not, return False.
Return True if all elements in arr match the elements in the corresponding pieces.

Implementation

Python solution:

 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:
        mapping = {piece[0]: piece for piece in pieces}
        i = 0
        while i < len(arr):
            if arr[i] not in mapping:
                return False
            piece = mapping[arr[i]]
            for value in piece:
                if value != arr[i]:
                    return False
                i += 1
        return True

Explanation

For Input: arr = [15,88], pieces = [[88],[15]]
Mapping: {15: [15], 88: [88]}
Iteration through arr: [15] then [88]
Output: true

This code ensures that each piece is used exactly as it appears in pieces and in the order that corresponds to arr. The complexity of this solution is ( O(n) ), where ( n ) is the length of arr, as it iterates through arr and performs constant-time operations for each element.