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 piecesin any order.
However, you are not allowed to reorder the integers in each array pieces[i].
Return trueif it is possibleto form the arrayarrfrompieces. Otherwise, return false.
Intuition:
We want to check if we can reconstruct arr by concatenating the subarrays in pieces in any order, but the order within each subarray must be preserved. Since all numbers are distinct, we can map the first element of each piece to the piece itself for fast lookup.
Approach:
Build a hash map from the first element of each piece to the piece.
Iterate through arr, and for each position, check if the current number is the start of a piece. If so, check if the next elements in arr match the piece.
If at any point the mapping fails, return false. If we finish, return true.
classSolution {
public:bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {
unordered_map<int, vector<int>> mp;
for (auto& p : pieces) mp[p[0]] = p;
int i =0, n = arr.size();
while (i < n) {
if (!mp.count(arr[i])) return false;
auto& v = mp[arr[i]];
for (int x : v) {
if (i >= n || arr[i] != x) return false;
i++;
}
}
return true;
}
};
classSolution {
publicbooleancanFormArray(int[] arr, int[][] pieces) {
Map<Integer, int[]> mp =new HashMap<>();
for (int[] p : pieces) mp.put(p[0], p);
int i = 0, n = arr.length;
while (i < n) {
if (!mp.containsKey(arr[i])) returnfalse;
int[] v = mp.get(arr[i]);
for (int x : v) {
if (i >= n || arr[i]!= x) returnfalse;
i++;
}
}
returntrue;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
classSolution {
funcanFormArray(arr: IntArray, pieces: Array<IntArray>): Boolean {
val mp = mutableMapOf<Int, IntArray>()
for (p in pieces) mp[p[0]] = p
var i = 0while (i < arr.size) {
val v = mp[arr[i]] ?:returnfalsefor (x in v) {
if (i >= arr.size || arr[i] != x) returnfalse i++ }
}
returntrue }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
classSolution:
defcanFormArray(self, arr: list[int], pieces: list[list[int]]) -> bool:
mp = {p[0]: p for p in pieces}
i, n =0, len(arr)
while i < n:
if arr[i] notin mp:
returnFalse v = mp[arr[i]]
for x in v:
if i >= n or arr[i] != x:
returnFalse i +=1returnTrue