Sponsored
Sponsored
In this approach, leverage a dictionary to map each number that starts a piece to the rest of the numbers in that piece. This allows us to quickly check if the numbers in arr can be sequentially matched with numbers in each piece in the correct order.
Time Complexity: O(n) where n is the number of elements in arr. Space Complexity: O(n) for storing the result list.
1def canFormArray(arr, pieces):
2 mapping = {p[0]: p for p in pieces}
3 result = []
4 for number in arr:
5 if number in mapping:
6 result.extend(mapping[number])
7 else:
8 return False
9 return result == arrThis Python solution creates a dictionary mapping that associates each starting number of a piece with the piece itself. It then iterates over the arr, extending the result list with the respective pieces. If any number is not found in the dictionary, it returns False. Finally, it checks if the constructed result list is equal to arr.
This approach focuses on direct sequential checking by maintaining a mapping of each starting index in arr to its corresponding pieces index, allowing direct comparison with sections of the arr.
Time Complexity: O(n) where n is the number of elements in arr. Space Complexity: O(m) where m is the size of the pieces data structure.
1#include <unordered_map>
2#include <vector>
3using namespace std;
4
5bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {
unordered_map<int, vector<int>> map;
for (auto& piece : pieces) {
map[piece[0]] = piece;
}
for (size_t i = 0; i < arr.size(); ) {
if (map.find(arr[i]) == map.end()) {
return false;
}
auto& piece = map[arr[i]];
for (int num : piece) {
if (num != arr[i++]) {
return false;
}
}
}
return true;
}This C++ implementation utilizes an unordered map to associate the starting number of each piece with the piece itself. It iterates through arr, checking the mapping to see if the next piece matches the sequence from the current index.