The given question is 1640 in the Leetcode and comes in the easy category of Leetcode.
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.
The solutions can be found here:
If any optimal solution is found, do comment here. Thank You
Now, let's study, what the question is,
You are given an array of distinct integer arr and an array of integer arrays, where the integer 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 piece [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++ Solution
class Solution {public:bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {vector<int> ps(101,-1);for(int i=0;i<pieces.size();i++) {ps[pieces[i][0]]=i;}for(int i=0;i<arr.size();) {int p=ps[arr[i]];if(p==-1) {return false;}for(int j=0;j<pieces[p].size();j++) {if(pieces[p][j]!=arr[i++])return false;}}return true;}};
Python 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 dictionary.
