Check Array Formation Through Concatenation

Problem Statement

In this problem, you are provided with two types of arrays: a single-dimensional array arr consisting of distinct integers and a secondary structure pieces, which is an array containing subarrays. Each subarray in pieces is composed of distinct integers, and you need to assemble the original array arr using these subarrays. The crucial point to note is that while the subarrays in pieces can be used in any sequence to reconstruct arr, the order of integers within each subarray must remain unchanged.

Your task is to determine if it is possible to reconstruct arr entirely by concatenating the subarrays from pieces without altering the order of integers within those subarrays. The function should return true if arr can be successfully formed, and false otherwise.

Examples

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

Example 3

Input:

arr = [91,4,64,78], pieces = [[78],[4,64],[91]]

Output:

true

Explanation:

Concatenate [91] then [4,64] then [78]

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

Approach and Intuition

Given the distinct nature of integers across arr and pieces, a strategic approach involves:

1. Mapping the starting integer of each subarray in pieces to its corresponding subarray. This is because every integer is unique across both arr and pieces, making it possible to instantly identify which subarray to use by looking at its starting integer.

2. Iterate over arr and for each integer, check if it marks the beginning of any subarray in pieces (as identified in the mapping). If it does, check if the subsequent elements in arr match this subarray.

   • If they match, skip the length of this subarray in arr and continue with the next integer.
   • If they do not match or if any integer in arr does not start any subarray in pieces, return false.

3. If you manage to validate all elements in arr against subarrays from pieces with the right order and without any leftovers, return true.

This approach leverages the uniqueness and fixed order of integers, making it both effective and highly efficient under the constraints provided.

Solutions

class Solution {
public:
    bool canAssembleArray(vector<int>& mainArray, vector<vector<int>>& subArrays) {
        int length = mainArray.size();
        unordered_map<int, vector<int>> arrayMap;
        // Populate the map with subArrays
        for (auto section: subArrays){
            arrayMap[section[0]] = section;
        }
    
        int index = 0;
        while (index < length) {
            // Check if current main array element is a start of some subArray
            if (arrayMap.count(mainArray[index]) == 0) {
                return false;
            }
            // Validate the sequence
            auto currentSection = arrayMap[mainArray[index]];
            for (int element : currentSection) {
                if (element != mainArray[index]) {
                    return false;
                }
                index++;
            }
        }
        return true;
    }
};