Leetcode — Check Array Formation Through Concatenation

The given question is 1640 in the Leetcode and comes in the easy category of Leetcode.

Now, let's study, what's the question s

You are given an array of distinct integers arr and an array of integer arrays, where the integers pieces are distinct. Your goal is to form arr by concatenating the arrays in pieces 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.

As per the given conditions, we are given an input array and pieces of the array. If the pieces are added(concatenate) to form an array, then we can return boolean true, else return false.

The given examples are as follows:

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]

The constraints are the most important aspect of the given question by which we can identify the time complexity of the given question and then we can go to a lower time complexity as per the expectations.

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

Since all elements are unique, we can map the first element in pieces to the piece position. Then, we just check if we have the right piece, and if so - try to fit it. As values are within [0..100], we can use an array instead of a hashmap.

Valid Explanation for the solution

C++

class Solution {
public:
    bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {
        map<int,vector<int>> mp; 
        // map the 1st element in pieces[i] to pieces[i]
        for(auto p:pieces) 
            mp[p[0]] = p;
        vector<int> result;
        for(auto a:arr) {
            if(mp.find(a)!=mp.end()) 
                result.insert(result.end(),mp[a].begin(),mp[a].end());
        }
        return result ==arr;
    }
};

For the given Solution, We have the Time complexity of O(N) where N is the size of the array, and the Auxillary Space Complexity of O(N) for creating a hashmap

Python

class Solution:
    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:
        keys, ans = {}, []
        for piece in pieces:
            keys[piece[0]] = piece
        for a in arr:
            if a in keys:
                ans.extend(keys[a])
        return ''.join(map(str, arr)) == ''.join(map(str, ans))

For the given Solution, We have the Time complexity of O(N) where N is the size of the array, and the Auxillary Space Complexity of O(N) for creating a hashmap.

If any optimal solution is found, do comment here.

Thank You