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 pieces in any order. However, you are not allowed to reorder the integers in each array pieces[i].
Return true if it is possible to form the array arr from pieces. Otherwise, return false.
Example 1:
Input: arr = [15,88], pieces = [[88],[15]] Output: true Explanation: Concatenate [15] then [88]
Example 2:
Input: arr = [49,18,16], pieces = [[16,18,49]] Output: false Explanation: Even though the numbers match, we cannot reorder pieces[0].
Example 3:
Input: arr = [91,4,64,78], pieces = [[78],[4,64],[91]] Output: true Explanation: Concatenate [91] then [4,64] then [78]
Constraints:
1 <= pieces.length <= arr.length <= 100sum(pieces[i].length) == arr.length1 <= pieces[i].length <= arr.length1 <= arr[i], pieces[i][j] <= 100arr are distinct.pieces are distinct (i.e., If we flatten pieces in a 1D array, all the integers in this array are distinct).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.
This 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.
Java
Time Complexity: O(n) where n is the number of elements in arr. Space Complexity: O(n) for storing the result list.
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.
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.
JavaScript
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.
| Approach | Complexity |
|---|---|
| Using a Dictionary to Map Start Elements | Time Complexity: O(n) where n is the number of elements in |
| Using Index Mapping and Sequential Checking | Time Complexity: O(n) where n is the number of elements in |
Leetcode 1640. Check Array Formation Through Concatenation • Fraz • 2,923 views views
Watch 9 more video solutions →Practice Check Array Formation Through Concatenation with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor