1640. Check Array Formation Through Concatenation
Model: qwen2.5-coder:14b
Topics: Array,Hash Table,Sort
FAANG asked: 0
Acceptance rate: 59.8%
Problem Breakdown
The problem asks us to determine if we can form an array arr by concatenating sub-arrays from another array of arrays called pieces. The integers in each sub-array within pieces must remain in the same order as they appear. We need to return true if it’s possible to form arr using any order of sub-arrays from pieces, otherwise, we return false.
Inputs:
arr: An array of distinct integers.pieces: An array of integer arrays where each sub-array contains distinct integers.
Outputs:
- A boolean value (
trueorfalse) indicating whetherarrcan be formed by concatenating the sub-arrays inpieces.
Implicit Constraints:
- The integers in
arrare distinct. - The integers in
piecesare distinct when flattened into a single array.
Intuition
A brute-force approach would involve checking every possible permutation of the sub-arrays in pieces to see if they can form arr. However, this approach is inefficient due to its factorial time complexity relative to the number of sub-arrays in pieces.
The key insight is that each sub-array in pieces must start with a unique integer. We can use a hash table (dictionary) to map these starting integers to their corresponding sub-arrays. This allows us to quickly check if a sub-array from pieces can be placed at the current position in arr.
Approach
- Create a Mapping: Use a dictionary to map the first element of each sub-array in
piecesto the sub-array itself. - Iterate Through
arr: For each element inarr, check if it is the start of any sub-array inpieces. - Check Sub-Array Match: If it matches, verify that the subsequent elements in
arrmatch the rest of the sub-array. - Return Result: If all elements in
arrcan be matched with sub-arrays frompieces, returntrue. Otherwise, returnfalse.
Complexity Analysis
- Time Complexity: O(n), where n is the length of
arr. We iterate througharronce and perform constant-time dictionary operations. - Space Complexity: O(m), where m is the total number of elements across all sub-arrays in
pieces. This is due to storing the mapping from starting integers to sub-arrays.
Solution
def canFormArray(arr, pieces):
# Create a dictionary to map the first element of each piece to the piece itself
piece_map = {piece[0]: piece for piece in pieces}
i = 0
while i < len(arr):
if arr[i] not in piece_map:
return False
piece = piece_map[arr[i]]
# Check if the current piece matches the next elements in arr
if arr[i:i + len(piece)] != piece:
return False
i += len(piece)
return True
Edge Cases Handled
- Single Element Array: If
arrhas only one element, the solution checks if that element is present as a single-element sub-array inpieces. - No Matching Sub-Array: If any element in
arrdoes not start a sub-array inpieces, the function returnsfalse. - Mismatched Sub-Array Lengths: If a sub-array from
piecesdoes not match the corresponding elements inarr, the function returnsfalse. - All Elements Match: If all elements in
arrcan be matched with sub-arrays frompieces, the function returnstrue.