Domain 1EasyCORE

Check Array Formation Through Concatenation

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`.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array#Hash Table#Sort

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 (true or false) indicating whether arr can be formed by concatenating the sub-arrays in pieces.

Implicit Constraints:

  • The integers in arr are distinct.
  • The integers in pieces are 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

  1. Create a Mapping: Use a dictionary to map the first element of each sub-array in pieces to the sub-array itself.
  2. Iterate Through arr: For each element in arr, check if it is the start of any sub-array in pieces.
  3. Check Sub-Array Match: If it matches, verify that the subsequent elements in arr match the rest of the sub-array.
  4. Return Result: If all elements in arr can be matched with sub-arrays from pieces, return true. Otherwise, return false.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of arr. We iterate through arr once 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 arr has only one element, the solution checks if that element is present as a single-element sub-array in pieces.
  • No Matching Sub-Array: If any element in arr does not start a sub-array in pieces, the function returns false.
  • Mismatched Sub-Array Lengths: If a sub-array from pieces does not match the corresponding elements in arr, the function returns false.
  • All Elements Match: If all elements in arr can be matched with sub-arrays from pieces, the function returns true.