Check Array Formation Through Concatenation

Difficulty: Easy | Acceptance: 57.30% | Paid: No Topics: Array, Hash Table

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 inside each piece pieces[i]. Return true if it is possible to form the array arr from pieces, otherwise return false.

• Examples
• Constraints
• Approach 1: Hash Map
• Approach 2: Brute Force

Examples

Input: arr = [15,88], pieces = [[88],[15]]
Output: true
Explanation: Concatenate [15] and [88] to get [15,88].

Input: arr = [49,18,16], pieces = [[16,18,49]]
Output: false
Explanation: Even though the numbers match, we cannot reorder pieces[0].

Input: arr = [91,4,64,78], pieces = [[78],[4,64],[91]]
Output: true
Explanation: Concatenate [91], [4,64], and [78] to get [91,4,64,78].

Constraints

1 <= pieces.length <= arr.length <= 100
sum(pieces[i].length) == arr.length
The integers in arr are distinct.
The integers in pieces are distinct (i.e., If we flatten pieces in a 1D array, all the integers in this array are distinct).

Approach 1: Hash Map

Intuition Since all integers in arr and pieces are distinct, the first element of any piece uniquely identifies that piece. We can use a hash map to store the mapping from the first element of a piece to the piece itself. Then, we iterate through arr and try to match elements sequentially using this map.

Steps

• Create a hash map where the key is the first element of a sub-array in pieces and the value is the sub-array itself.
• Initialize an index i to 0 to traverse arr.
• While i is less than the length of arr:
  • Check if arr[i] exists in the map. If not, return false.
  • Retrieve the corresponding piece from the map.
  • Iterate through the retrieved piece and compare each element with the corresponding elements in arr starting at i.
  • If any element does not match, return false.
  • Increment i by the length of the piece.
• If the loop completes successfully, return true.

class Solution:
    def canFormArray(self, arr: list[int], pieces: list[list[int]]) -> bool:
        mapping = {p[0]: p for p in pieces}
        i = 0
        while i < len(arr):
            if arr[i] not in mapping:
                return False
            piece = mapping[arr[i]]
            # Check if the slice of arr matches the piece
            if arr[i:i+len(piece)] != piece:
                return False
            i += len(piece)
        return True

Complexity

• Time: O(N), where N is the length of arr. We visit each element in arr exactly once.
• Space: O(N), to store the hash map of pieces.
• Notes: This is the optimal approach for this problem.

Approach 2: Brute Force

Intuition We can iterate through the arr and for every element, we search through the list of pieces to find a piece that starts with that element. Once found, we verify the rest of the elements in that piece.

Steps

• Initialize an index i to 0.
• While i is less than the length of arr:
  • Iterate through pieces to find a piece p such that p[0] == arr[i].
  • If no such piece is found, return false.
  • Iterate through the found piece p and compare elements with arr starting at i.
  • If any mismatch occurs, return false.
  • Increment i by the length of p.
• Return true if the loop finishes.

class Solution:
    def canFormArray(self, arr: list[int], pieces: list[list[int]]) -> bool:
        i = 0
        n = len(arr)
        while i < n:
            found = False
            for p in pieces:
                if p and p[0] == arr[i]:
                    # Check if the rest matches
                    if arr[i:i+len(p)] != p:
                        return False
                    i += len(p)
                    found = True
                    break
            if not found:
                return False
        return True

Complexity

• Time: O(N * M), where N is the length of arr and M is the number of pieces. In the worst case, we scan all pieces for every element in arr.
• Space: O(1), excluding the input storage, as we do not use extra data structures proportional to the input size.
• Notes: This approach is less efficient than the Hash Map approach but uses constant extra space.