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