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.
1function canFormArray(arr, pieces) {
2This JavaScript approach uses a Map object to store pieces indexed by their first items. It iterates over arr, using the map to check for an ordered subarray at each index.