Problem Description

You are given two arrays, arr and pieces:

• arr is a 1D array of distinct positive integers.
• pieces is a 2D array where each subarray is a sequence of distinct positive integers (also all values are distinct across all subarrays).

• Each element in arr and across all pieces is unique.
• Each pieces[i] can only be used once and must be used as a whole (no splitting or reordering inside).
• There is at most one valid way to form arr from pieces.

Thought Process

At first glance, one might consider generating all possible orderings of the pieces arrays and checking if any concatenation matches arr. However, this brute-force approach would be very inefficient, as the number of permutations grows rapidly with the number of subarrays.

Instead, let's focus on the constraints:

• Each number is unique and appears only once in arr and pieces.
• Within each subarray in pieces, the order must be preserved.
• We cannot split or reorder the subarrays in pieces.

Solution Approach

Let's break down the steps for an efficient solution:

1. Build a mapping: Create a hash map (dictionary) from the first element of each subarray in pieces to the subarray itself. This allows us to quickly check, for any number in arr, whether it is the start of a subarray.
2. Iterate through arr: Use a pointer to move through arr. At each position, check if arr[i] is the first element of any subarray in pieces (using our hash map).
3. Match subarrays: If there is a matching subarray, check if the next len(subarray) elements in arr exactly match the subarray. If not, return false.
4. Advance the pointer: If there's a match, move the pointer in arr forward by the length of the subarray.
5. Repeat until the end: Continue this process until we've checked all elements in arr. If we reach the end without a mismatch, return true.

Example Walkthrough

Example:
arr = [85, 1, 2, 3, 4]
pieces = [[85], [1,2], [3,4]]

Step-by-step:

• Build the hash map: {85: [85], 1: [1,2], 3: [3,4]}
• Start at arr[0] = 85. 85 is the start of [85], which matches arr[0]. Move pointer to arr[1].
• arr[1] = 1. 1 is the start of [1,2]. Check if arr[1:3] = [1,2] matches [1,2]. Yes. Move pointer to arr[3].
• arr[3] = 3. 3 is the start of [3,4]. Check if arr[3:5] = [3,4] matches [3,4]. Yes. Move pointer to arr[5], which is out of bounds.
• We've reached the end of arr with all matches. Return true.

Time and Space Complexity

Brute-force approach:
- Try all permutations of pieces and concatenate them, checking if any match arr.
- Time complexity: O(k! * n), where k is the number of subarrays and n is the length of arr.
- Space complexity: O(n) for each concatenation.

Optimized approach:
- Build the hash map: O(k), where k is the number of subarrays in pieces.
- Iterate through arr once: O(n). For each position, we do an O(1) lookup and up to O(m) comparisons, where m is the maximum length of a subarray (but each element is only checked once in total).
- Space complexity: O(k) for the hash map.
Overall: O(n) time and O(k) space.

Summary

By leveraging the uniqueness of numbers and the structure of pieces, we avoid brute-force permutations. Instead, we use a hash map to quickly match subarrays as we traverse arr. This efficient, greedy approach ensures each subarray is matched in order, resulting in a linear-time solution that is both simple and robust. The elegance lies in recognizing that each subarray can be matched directly by mapping its first element, turning a potentially complex permutation problem into a straightforward scan.

Code Implementation

class Solution:
    def canFormArray(self, arr, pieces):
        first_elem_map = {piece[0]: piece for piece in pieces}
        i = 0
        n = len(arr)
        while i < n:
            if arr[i] not in first_elem_map:
                return False
            piece = first_elem_map[arr[i]]
            if arr[i:i+len(piece)] != piece:
                return False
            i += len(piece)
        return True
      

class Solution {
public:
    bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {
        unordered_map<int, vector<int>> firstElemMap;
        for (auto& piece : pieces) {
            firstElemMap[piece[0]] = piece;
        }
        int i = 0, n = arr.size();
        while (i < n) {
            if (firstElemMap.find(arr[i]) == firstElemMap.end())
                return false;
            vector<int>& piece = firstElemMap[arr[i]];
            for (int j = 0; j < piece.size(); ++j) {
                if (i + j >= n || arr[i + j] != piece[j])
                    return false;
            }
            i += piece.size();
        }
        return true;
    }
};
      

class Solution {
    public boolean canFormArray(int[] arr, int[][] pieces) {
        Map<Integer, int[]> firstElemMap = new HashMap<>();
        for (int[] piece : pieces) {
            firstElemMap.put(piece[0], piece);
        }
        int i = 0;
        while (i < arr.length) {
            if (!firstElemMap.containsKey(arr[i])) {
                return false;
            }
            int[] piece = firstElemMap.get(arr[i]);
            for (int j = 0; j < piece.length; ++j) {
                if (i + j >= arr.length || arr[i + j] != piece[j]) {
                    return false;
                }
            }
            i += piece.length;
        }
        return true;
    }
}
      

var canFormArray = function(arr, pieces) {
    const firstElemMap = new Map();
    for (const piece of pieces) {
        firstElemMap.set(piece[0], piece);
    }
    let i = 0;
    while (i < arr.length) {
        if (!firstElemMap.has(arr[i])) {
            return false;
        }
        const piece = firstElemMap.get(arr[i]);
        for (let j = 0; j < piece.length; ++j) {
            if (arr[i + j] !== piece[j]) {
                return false;
            }
        }
        i += piece.length;
    }
    return true;
};