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.
1import java.util.HashMap;
2
3public boolean canFormArray(int[] arr, int[][] pieces) {
4 HashMap<Integer, int[]> map = new HashMap<>();
5 for (int[] piece : pieces) {
6 map.put(piece[0], piece);
7 }
8 int index = 0;
9 while (index < arr.length) {
10 if (!map.containsKey(arr[index])) {
11 return false;
12 }
13 int[] piece = map.get(arr[index]);
14 for (int num : piece) {
15 if (num != arr[index++]) {
16 return false;
17 }
18 }
19 }
20 return true;
21}This Java solution uses a HashMap to store each piece mapped by its starting integer. As we iterate through arr, we check if each number is the starting number of a piece, retrieving and verifying if the sequence matches arr. If any sequence breaks, it returns false.
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.