Leetcode – Check Array Formation Through Concatenation Solution

Spread the love

The “Check Array Formation Through Concatenation” problem on Leetcode is a thought-provoking challenge that requires a good understanding of array manipulation and algorithmic thinking. The problem sits at the intersection of various programming concepts like searching, slicing, and data structure utilization, making it an interesting study.

In this extensive article, we will dissect the problem’s requirements, examine multiple approaches to solve it, delve into their time and space complexity, and implement the solutions in Python.

Problem Description

The problem statement is as follows:

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 in the individual arrays pieces[i].

Return True if it is possible to form the array arr from pieces. Otherwise, return False.

Example

canFormArray([85, 15, 105], [[105], [15], [85]])  # Output: True

Approach 1: Hash Map Lookup

Algorithm

  1. Create a hash map (dictionary) from the pieces array to make lookups efficient.
  2. Iterate through the arr while looking up the first element of each subarray in pieces.
  3. If found, check the subsequent elements in arr with those in the found piece and skip them.

Python Code

from typing import List

def canFormArray(arr: List[int], pieces: List[List[int]]) -> bool:
    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]]
        for num in piece:
            if i < len(arr) and arr[i] == num:
                i += 1
            else:
                return False
    return True

Time Complexity

The time complexity for this approach is O(n), where n is the length of the array arr.

Space Complexity

The space complexity is O(m), where m is the number of individual pieces.

Approach 2: String Conversion

Algorithm

  1. Convert the arr and each piece in pieces to strings.
  2. Check if the string of arr can be formed by the concatenation of strings of pieces.

Python Code

def canFormArray(arr: List[int], pieces: List[List[int]]) -> bool:
    arr_str = ''.join(map(str, arr))
    pieces_str = ["".join(map(str, piece)) for piece in pieces]
    
    for piece_str in pieces_str:
        arr_str = arr_str.replace(piece_str, "")
        
    return not arr_str

Time Complexity

The time complexity is O(n), but with a larger constant factor due to string operations.

Space Complexity

The space complexity is O(n) due to the storage required for string conversion.

Conclusion

The “Check Array Formation Through Concatenation” problem on Leetcode allows us to explore interesting algorithms and techniques related to array manipulation. We discussed two different approaches: one using hash map lookups and another using string conversion. Both methods have their merits and trade-offs in terms of time and space complexity.

Leave a Reply