# Check Array Formation Through Concatenation

Problem Statement

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

Example 2:

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

Example 3:

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

Example 4:

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

Example 5:

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

Constraints:

• `1 <= pieces.length <= arr.length <= 100`

Solution Using C# Dictionary -

Algorithm

Step 1: Initialize a Dictionary mapping to record piece’s first integer and the whole piece array.
Step 2: Initialize an index i to record the current matching index in arr.
Step 3: Find the piece starting with arr[i] in mapping. Return false if no match.
Step 4: Use the matched piece to match piece[] sublist starting from i with the same length. Return false if any integer is different.
Step 5: Increment the index i.
Step 6: Repeat until i reach the end of arr. Return true.

Complexity Analysis :

• Time Complexity: O(N).

Using no extra space -

Full Stack Programmer, love to solve problem’s during free time.

## More from Jaydeep

Full Stack Programmer, love to solve problem’s during free time.