We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Check Array Formation Through Concatenation

Number: 1760

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given an array of distinct integers arr and a collection of integer arrays pieces (with distinct integers overall), determine if arr can be formed by concatenating the arrays in pieces in any order while keeping the order of integers in each individual piece unchanged.

Key Insights

  • Each integer in arr is unique; similarly, every integer in pieces is unique across all pieces.
  • Use a hash map (or dictionary) to map the first element of each piece to the corresponding array.
  • Iterate through arr, and for each element, if it exists as the key in our hash map, validate that the following segment in arr exactly matches the corresponding piece.
  • If any element in arr does not match the start of a piece or the sequence does not match, return false.

Space and Time Complexity

Time Complexity: O(n), where n is the length of arr, since each element is processed exactly once. Space Complexity: O(m), where m is the number of pieces, due to the extra hash map.

Solution

To solve the problem, we first construct a hash map that associates the first integer of each piece with the piece itself. Then, using a pointer, we traverse arr. For each arr element, we check whether it is the starting element of a piece by looking it up in the hash map. If found, we validate that the subsequent numbers in arr match the entire piece. If there is any mismatch or an element in arr isn't found as a key in the map, we return false. If we successfully process all elements in arr, we return true. This approach efficiently leverages a hash map to match pieces in O(n) time without reordering the individual pieces.

Code Solutions

def canFormArray(arr, pieces):
    # Build a hash map: key is the first element of the piece, value is the piece itself.
    piece_map = {piece[0]: piece for piece in pieces}
    i = 0
    # Iterate through the array arr.
    while i < len(arr):
        # If the current element is not the start of any piece, return False.
        if arr[i] not in piece_map:
            return False
        # Retrieve the corresponding piece.
        piece = piece_map[arr[i]]
        # Check if the segment in arr matches the piece exactly.
        for number in piece:
            # If mismatch occurs or index out-of-bound, return False.
            if i < len(arr) and arr[i] == number:
                i += 1
            else:
                return False
    return True
← Back to All Questions