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.
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.