algoadvance

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 the array arr by concatenating the arrays in pieces in any order. However, you cannot reorder the integers in each subarray in pieces.

Return True if you can form the array arr by concatenating the arrays in pieces. Otherwise, return False.

Clarifying Questions

  1. Are the integers in arr and each subarray of pieces unique?
    • Yes, all integers in arr and pieces are distinct.
  2. Can the pieces be used only once?
    • Yes, each subarray in pieces can only be used once.
  3. What are the constraints on the lengths of arr and pieces?
    • The length of arr is in the range [1, 100].
    • The length of each subarray in pieces is in the range [1, 100].

With these clarifications in mind, let’s plan our solution.

Strategy

To solve this problem, we will follow these steps:

  1. Create a dictionary that maps the first element of each subarray in pieces to the subarray itself.
  2. Iterate through arr while trying to match each segment of arr with one of the subarrays in pieces as denoted by the dictionary.
  3. If at any point there is no matching subarray or if a piece of the array doesn’t conform to any subarray, return False.
  4. If we successfully iterate through the entire arr, return True.

Code

def can_form_array(arr, pieces):
    # Create a dictionary with the first element of each subarray in pieces as the key
    piece_dict = {piece[0]: piece for piece in pieces}
    
    i = 0
    while i < len(arr):
        if arr[i] not in piece_dict:
            return False
        
        piece = piece_dict[arr[i]]
        # Check if the piece matches the segment of arr starting at index i
        if arr[i:i+len(piece)] != piece:
            return False
        
        i += len(piece)
    
    return True

# Example Usage
arr = [85, 1, 2, 3, 101]
pieces = [[85], [1, 2, 3], [101]]
print(can_form_array(arr, pieces))  # Expected Output: True

Time Complexity

Thus, the final time complexity of the solution is (O(m + n)) which is efficient given the problem constraints.

Try our interview co-pilot at AlgoAdvance.com