Problem Description

You are given two arrays:

• arr: an array of distinct integers
• pieces: an array containing multiple integer arrays, where all integers across all pieces are distinct

Your task is to determine if you can reconstruct the array arr by concatenating the arrays in pieces in some order.

Key constraints:

1. You can use the arrays in pieces in any order you want
2. You cannot rearrange the elements within each individual piece - they must stay in their original order
3. Each piece can only be used once (or not at all)
4. All integers in the problem are distinct

Example scenarios:

• If arr = [1,3,5,7] and pieces = [[5,7],[1,3]], you can form arr by concatenating [1,3] first, then [5,7], so return true
• If arr = [1,2,3] and pieces = [[1],[3,2]], you cannot form arr because you'd need to rearrange [3,2] to [2,3], which is not allowed, so return false

The solution works by iterating through arr and for each position, finding a piece that starts with the current element. If found, it verifies that the entire piece matches the subsequent elements in arr in the exact order. If at any point a matching piece cannot be found or a piece doesn't match completely, it returns false. If the entire arr is successfully matched, it returns true.

Intuition

The key insight is that since all integers are distinct and we cannot reorder elements within each piece, each element in arr uniquely determines which piece (if any) must be used at that position.

When we encounter an element in arr, we need to find the piece that starts with that element. Since elements are distinct, at most one piece can start with any given element. Once we find such a piece, we must use the entire piece in its original order - we can't skip elements or rearrange them.

This leads to a greedy approach:

1. Start from the beginning of arr
2. For the current element, find which piece starts with it
3. If no piece starts with it, we can't form arr (return false)
4. If we find a matching piece, verify that the entire piece matches the next consecutive elements in arr
5. Move forward in arr by the length of the matched piece
6. Repeat until we've processed all of arr

The reason this greedy approach works is because of the distinct elements constraint. Each element in arr has only one possible piece that can provide it (the piece containing that element). And since we can't reorder within pieces, once we commit to using a piece at a certain position, we must use all of its elements consecutively. There's no benefit to delaying the use of a piece - if it fits now, use it now.

The algorithm essentially treats each piece as an indivisible block that must be placed whole, and the distinct elements constraint means there's only one valid way to match pieces to positions in arr.

Solution Approach

The solution uses a two-pointer traversal approach with nested loops to match pieces to segments of the array.

Implementation walkthrough:

1. Main traversal pointer i: We maintain a pointer i that tracks our current position in arr. This pointer advances as we successfully match pieces.

2. Finding matching pieces: For each position i in arr, we search through all pieces to find one that starts with arr[i]:

   k = 0
   while k < len(pieces) and pieces[k][0] != arr[i]:
       k += 1

   This linear search checks the first element of each piece until we find a match.

3. No match found: If k == len(pieces), it means we've searched all pieces and none starts with arr[i]. This makes it impossible to form arr, so we return false.

4. Verifying the entire piece: Once we find a matching piece at index k, we need to verify that the entire piece matches consecutive elements in arr:

   j = 0
   while j < len(pieces[k]) and arr[i] == pieces[k][j]:
       i, j = i + 1, j + 1

   This simultaneous traversal compares each element of pieces[k] with corresponding elements in arr, advancing both pointers together.

5. Automatic validation: The inner while loop exits when either:

   • We've matched the entire piece (j == len(pieces[k])) - success, continue with next segment
   • We found a mismatch (arr[i] != pieces[k][j]) - the loop exits but i has already advanced partially, and the next iteration of the outer loop will fail to find a piece starting with this mismatched element

6. Final check: If we successfully process all elements of arr (the outer while loop completes with i == len(arr)), we return true.

Time Complexity: O(n × m) where n is the length of arr and m is the number of pieces, as we might search through all pieces for each element.

Space Complexity: O(1) as we only use a constant amount of extra space for pointers.

Example Walkthrough

Let's walk through the solution with arr = [91, 4, 64, 78] and pieces = [[78], [4, 64], [91]].

Step 1: Initialize pointer i = 0

• Current element: arr[0] = 91
• Search through pieces for one starting with 91:
  • pieces[0][0] = 78 ❌
  • pieces[1][0] = 4 ❌
  • pieces[2][0] = 91 ✓
• Found matching piece [91] at index k = 2

Step 2: Verify and consume the piece

• Compare pieces[2] with arr starting at position 0:
  • pieces[2][0] = 91 vs arr[0] = 91 ✓
• Entire piece matched! Advance i by length of piece: i = 0 + 1 = 1

Step 3: Continue with i = 1

• Current element: arr[1] = 4
• Search through pieces for one starting with 4:
  • pieces[0][0] = 78 ❌
  • pieces[1][0] = 4 ✓
• Found matching piece [4, 64] at index k = 1

Step 4: Verify and consume the piece

• Compare pieces[1] with arr starting at position 1:
  • pieces[1][0] = 4 vs arr[1] = 4 ✓
  • pieces[1][1] = 64 vs arr[2] = 64 ✓
• Entire piece matched! Advance i by length of piece: i = 1 + 2 = 3

Step 5: Continue with i = 3

• Current element: arr[3] = 78
• Search through pieces for one starting with 78:
  • pieces[0][0] = 78 ✓
• Found matching piece [78] at index k = 0

Step 6: Verify and consume the piece

• Compare pieces[0] with arr starting at position 3:
  • pieces[0][0] = 78 vs arr[3] = 78 ✓
• Entire piece matched! Advance i by length of piece: i = 3 + 1 = 4

Step 7: Check completion

• i = 4 equals len(arr) = 4
• We've successfully matched all elements!
• Return true

The array can be formed by concatenating pieces in the order: [91] + [4, 64] + [78] = [91, 4, 64, 78]

Solution Implementation

Time and Space Complexity

Time Complexity: O(n * m) where n is the length of arr and m is the number of pieces in pieces.

The outer while loop iterates through each element of arr once, giving us O(n) iterations. For each element in arr, we search through the pieces list to find a matching piece that starts with the current element. This search takes O(m) time in the worst case. Once a matching piece is found, we iterate through that piece to verify it matches the corresponding elements in arr, but this verification is bounded by the total number of elements across all pieces, which equals n (since all pieces together must form the array). Therefore, the overall time complexity is O(n * m).

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space. The variables i, j, and k are the only additional memory used, regardless of the input size. The algorithm operates directly on the input arrays without creating any additional data structures.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Inefficient Piece Lookup Leading to Poor Performance

The current solution performs a linear search through all pieces for every position in arr, resulting in O(n × m) time complexity. When dealing with large inputs, this becomes a significant bottleneck.

Why it's a problem:

• For each element in arr, we potentially scan through all pieces
• The same pieces are searched multiple times
• This approach doesn't leverage the fact that all integers are distinct

Better Solution: Use a hashmap to map the first element of each piece to the piece itself, reducing lookup time from O(m) to O(1).

class Solution:
    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:
        # Create a mapping from first element to piece
        piece_map = {piece[0]: piece for piece in pieces}
      
        arr_index = 0
        while arr_index < len(arr):
            # O(1) lookup instead of O(m) search
            if arr[arr_index] not in piece_map:
                return False
          
            # Get the matching piece
            current_piece = piece_map[arr[arr_index]]
          
            # Verify the entire piece matches
            for element in current_piece:
                if arr_index >= len(arr) or arr[arr_index] != element:
                    return False
                arr_index += 1
      
        return True

2. Not Handling Edge Cases with Boundary Checks

A subtle pitfall occurs when verifying if a piece matches: the original code increments arr_index inside the verification loop without explicitly checking if we've exceeded array bounds.

Why it's problematic: While the current implementation handles this implicitly through the loop condition, it can lead to confusion and potential bugs if the logic is modified.

Clearer Solution: Explicitly check if the remaining elements in arr are sufficient to match the piece:

# Before matching a piece, verify there are enough elements left
if arr_index + len(current_piece) > len(arr):
    return False

# Then perform the matching
for element in current_piece:
    if arr[arr_index] != element:
        return False
    arr_index += 1

This makes the boundary checking explicit and the code more maintainable.