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).Problem Overview: You are given an integer array arr and a list of subarrays pieces. The task is to determine whether arr can be formed by concatenating these pieces without reordering elements inside each piece. Pieces can appear in any order, but their internal sequence must stay intact.
Approach 1: Using a Dictionary to Map Start Elements (O(n) time, O(n) space)
The key observation: every piece starts with a unique value. Build a hash map where the key is the first element of each piece and the value is the piece itself. Then iterate through arr. Whenever you see a number, check if it exists in the map. If it does, retrieve the corresponding piece and verify each element matches the sequence in arr. Move the pointer forward by the length of that piece. If a number in arr does not start any piece, the formation is impossible.
This works because hash lookups run in constant time. Instead of scanning all pieces repeatedly, you directly jump to the correct piece using the first element as the identifier. The algorithm performs a single pass over arr with occasional sequential checks inside pieces, keeping the overall complexity linear. This approach heavily relies on hash table lookups and sequential traversal of the array.
Approach 2: Using Index Mapping and Sequential Checking (O(n) time, O(n) space)
Another way to structure the same idea is by building an index map from each value in arr to its position. Then iterate through each piece and verify that its elements appear consecutively in arr. For the first element of a piece, retrieve its index using the map. Then check the remaining elements to ensure they follow immediately after in arr. If any mismatch occurs or the sequence breaks, return false.
This approach focuses on validating each piece independently instead of scanning the main array. The index map enables constant-time position lookup, while sequential checks confirm the order constraint. The logic is straightforward and works well when you prefer validating pieces rather than walking through the main array.
Recommended for interviews: The dictionary-based scan is typically the expected solution. It demonstrates efficient use of a hash map and linear traversal of the input. Interviewers like it because it shows you recognized the unique starting element property and avoided unnecessary nested loops. Understanding both methods helps: the index-mapping variant shows the same idea from a different angle and reinforces how hash-based indexing simplifies sequence validation problems.
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.
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.
C++
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.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| 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 |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dictionary Mapping by First Element | O(n) | O(n) | Best general solution. Efficient single pass with constant-time hash lookups. |
| Index Mapping and Sequential Check | O(n) | O(n) | Useful when validating each piece independently using array index positions. |
Leetcode 1640. Check Array Formation Through Concatenation • Fraz • 2,975 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