Check Array Formation Through Concatenation

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

Key Insights

• The elements in pieces must appear in arr in the same order as they do in the subarrays.
• A mapping of the starting indices of each piece in arr can help determine if the concatenation is valid.
• The problem can be solved using a hash table (dictionary) to map each starting element of pieces to its corresponding subarray.

Space and Time Complexity

Time Complexity: O(n), where n is the length of arr. We traverse arr and pieces once. Space Complexity: O(m), where m is the number of pieces, for storing the mapping of starting elements to their respective subarrays.

Solution

To determine if arr can be formed by concatenating the arrays in pieces, we can follow these steps:

1. Create a mapping from the first element of each piece to the piece itself.
2. Iterate through arr to check if the current element is the start of a piece.
3. If it is, verify that the subsequent elements in arr match the elements in the corresponding piece.
4. If all elements in arr can be accounted for by pieces without reordering, return true. Otherwise, return false.

Code Solutions