Solution Explanation

This problem asks whether we can form the array arr by concatenating the arrays in pieces in any order, without reordering elements within each sub-array in pieces. Both solutions leverage the fact that the integers in arr and pieces are distinct.

Approach 1: Iterative Matching

This approach iterates through arr. For each element in arr, it searches for a sub-array in pieces that starts with this element. If found, it verifies that the subsequent elements in arr match the remaining elements of the sub-array. If a match is found, the index i is advanced to the next element after the matched sub-array; otherwise, the function immediately returns false.

Time Complexity: O(N*M), where N is the length of arr and M is the total number of elements in pieces. In the worst case, we might iterate through all elements of pieces for each element in arr.

Space Complexity: O(1), as we only use a few integer variables for indexing.

Approach 2: Hash Map for Quick Lookup

This approach uses a hash map (dictionary in Python) to store the sub-arrays in pieces, keyed by their first element. This allows for O(1) lookup time to find a matching sub-array. The rest of the logic remains similar to Approach 1, checking for consecutive matches.

Time Complexity: O(N+M), where N is the length of arr and M is the total number of elements across all arrays in pieces. The creation of the hash map is O(M), and the iteration is O(N). Lookup in the hash map is O(1) on average.

Space Complexity: O(M), to store the hash map of sub-arrays in pieces.

Code Explanation (Python)

Both Python solutions are provided; I will explain Solution 2 (using the hashmap) as it's more efficient.

class Solution:
    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:
        d = {p[0]: p for p in pieces}  # Create a hash map for O(1) lookup
        i, n = 0, len(arr)
        while i < n:
            if arr[i] not in d:  # Check if current element is a start of a piece
                return False      # If not found, it's impossible to form arr
            p = d[arr[i]]       # Retrieve the piece starting with the element
            if arr[i : i + len(p)] != p: #Check if this piece matches arr
                return False          # If no match, return false
            i += len(p)            # Advance the index by the length of the matched piece
        return True                 # If all pieces are matched, return True

The code first creates a dictionary d where keys are the first elements of the sub-arrays in pieces and values are the sub-arrays themselves. The while loop iterates through arr, checking if each element is a key in d. If it is, it verifies if the subsequent elements in arr match the corresponding sub-array. If there is a mismatch at any point, or if an element is not found as a key in d, the function returns False. If the loop completes without finding any mismatches, it means all the sub-arrays can be concatenated to form arr, and the function returns True.

The other languages' solutions follow a similar logic, adapting the data structures (hash maps or dictionaries) to their respective languages. The key improvement of Solution 2 over Solution 1 is the use of the hash map for significantly faster lookup of sub-arrays in pieces.