# Check Array Formation Through Concatenation
**Difficulty:** EASY
[External](https://leetcode.com/problems/check-array-formation-through-concatenation)
Canonical: https://scaleengineer.com/dsa/problems/check-array-formation-through-concatenation
**Data structures:** Array, Hash Table
---
## Problem
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 each array `pieces[i]`.

Return `true` _if it is possible_ _to form the array_ `arr` _from_ `pieces`. Otherwise, return `false`.

**Example 1:**

**Input:** arr = [15,88], pieces = [[88],[15]]
**Output:** true
**Explanation:** Concatenate [15] then [88]

**Example 2:**

**Input:** arr = [49,18,16], pieces = [[16,18,49]]
**Output:** false
**Explanation:** Even though the numbers match, we cannot reorder pieces[0].

**Example 3:**

**Input:** arr = [91,4,64,78], pieces = [[78],[4,64],[91]]
**Output:** true
**Explanation:** Concatenate [91] then [4,64] then [78]

**Constraints:**

* `1 <= pieces.length <= arr.length <= 100`
* `sum(pieces[i].length) == arr.length`
* `1 <= pieces[i].length <= arr.length`
* `1 <= arr[i], pieces[i][j] <= 100`
* The integers in `arr` are **distinct**.
* The integers in `pieces` are **distinct** (i.e., If we flatten pieces in a 1D array, all the integers in this array are distinct).

# Approaches
## Brute-Force Iteration
This approach involves a straightforward, brute-force search. We iterate through the target array `arr` with a pointer. At each position, we search through the entire `pieces` array to find a piece that can start at the current position. If a potential piece is found, we verify if it perfectly matches the corresponding segment in `arr`. If it does, we advance our pointer and repeat the process. If no matching piece is found at any point, we conclude that `arr` cannot be formed.
**Time:** O(M^2 + N), where N is the length of `arr` and M is the number of pieces. The main `while` loop runs M times in total (once for each piece that forms `arr`). In each iteration of the `while` loop, we might iterate through all M pieces to find the one that starts with `arr[i]`. This search contributes O(M^2) to the complexity. The element-wise comparisons across all successful matches sum up to N comparisons in total. Thus, the overall complexity is O(M^2 + N). · **Space:** O(1), as no additional data structures are used. The space required is limited to a few variables to keep track of the current index and state, which does not depend on the input size.
**Pros:** It uses constant extra space, O(1), as it only requires a few variables for indexing and flags.
**Cons:** The time complexity is relatively high due to the nested iteration. For each segment of `arr` that needs to be matched, the algorithm scans the entire `pieces` array.
### Explanation
The core idea is to build the `arr` from left to right. We use an index `i` to keep track of our progress in `arr`. While `i` hasn't reached the end of `arr`, we look for a piece that can be placed at `arr[i]`. We do this by iterating through all the arrays in `pieces`. If we find a `piece` whose first element is `arr[i]`, we then check if the rest of that `piece`'s elements match the subsequent elements in `arr`. Because all numbers are distinct, there can be at most one such starting piece. If the piece doesn't fully match the segment in `arr`, we can immediately return `false`. If it does match, we advance our index `i` by the length of the matched piece and continue our search for the next piece. If we ever fail to find a piece that starts with `arr[i]`, we also return `false`. If we successfully reach the end of `arr`, we return `true`.

```java
class Solution {
    public boolean canFormArray(int[] arr, int[][] pieces) {
        int i = 0;
        while (i < arr.length) {
            boolean foundPiece = false;
            for (int[] piece : pieces) {
                if (piece[0] == arr[i]) {
                    foundPiece = true;
                    // Check if the rest of the piece matches
                    for (int j = 0; j < piece.length; j++) {
                        if (i + j >= arr.length || arr[i + j] != piece[j]) {
                            return false;
                        }
                    }
                    i += piece.length;
                    break; // Move to the next segment of arr
                }
            }
            if (!foundPiece) {
                return false; // No piece starts with arr[i]
            }
        }
        return true;
    }
}
```
### Algorithm
- Initialize a pointer `i` to 0, which will track the current position in `arr`.
- Loop as long as `i` is less than the length of `arr`.
- Inside the loop, initialize a boolean flag `foundMatch` to `false`.
- Iterate through each `piece` in the `pieces` array.
  - If the first element of the current `piece` matches `arr[i]`:
    - Set `foundMatch` to `true`.
    - Verify that the entire `piece` matches the corresponding segment in `arr` starting from `i`.
    - If any element does not match, it's impossible to form `arr`, so return `false`.
    - If the entire `piece` matches, advance `i` by the length of the `piece` and break the inner loop to move to the next segment of `arr`.
- After the inner loop, if `foundMatch` is still `false`, it means no piece starts with `arr[i]`. Return `false`.
- If the outer loop completes, it means `i` has reached the end of `arr`, and the array has been successfully formed. Return `true`.

## Optimized Approach using Hash Map
This optimized approach significantly improves the time efficiency by using a hash map. Instead of repeatedly searching the `pieces` array, we first pre-process it by storing all pieces in a hash map. The key for each piece is its first element. This allows us to find the correct piece for any given starting number in constant time on average. We then iterate through `arr`, and for each segment, we use the map to instantly find the corresponding piece and verify the match.
**Time:** O(N + M), where N is the length of `arr` and M is the number of pieces. Building the map takes O(M) time. The subsequent traversal of `arr` involves one lookup and one comparison for each element of `arr`. Since the total number of elements is N, this part takes O(N) time. Therefore, the total time complexity is O(N + M). Given that M <= N, this can be simplified to O(N). · **Space:** O(N), where N is the total number of elements in `pieces` (which equals `arr.length`). The hash map stores M key-value pairs, where M is the number of pieces. The keys and references take O(M) space, and the pieces themselves (which the map values refer to) contain N elements in total.
**Pros:** Very efficient time complexity, as finding the correct piece is an O(1) operation on average.; The logic is straightforward once the hash map is built.
**Cons:** This approach requires extra space to store the hash map. The space complexity is proportional to the number of pieces and their total length.
### Explanation
The bottleneck in the brute-force approach is the linear scan to find the right piece. We can eliminate this by using a hash map. We create a map where keys are the first elements of the pieces and values are the piece arrays themselves. This map can be built by iterating through `pieces` once.

After building the map, we iterate through `arr` using an index `i`. For each `arr[i]`, we check if it exists as a key in our map. If not, no piece starts with this number, and we can't form `arr`, so we return `false`. If it does exist, we retrieve the piece and verify that it matches the subarray in `arr` starting at `i`. If it matches, we advance `i` by the length of that piece. If it doesn't match, we return `false`. If we successfully process the entire `arr`, we return `true`.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean canFormArray(int[] arr, int[][] pieces) {
        Map<Integer, int[]> map = new HashMap<>();
        for (int[] piece : pieces) {
            map.put(piece[0], piece);
        }

        int i = 0;
        while (i < arr.length) {
            if (!map.containsKey(arr[i])) {
                return false;
            }
            
            int[] piece = map.get(arr[i]);
            for (int val : piece) {
                if (i >= arr.length || arr[i] != val) {
                    return false;
                }
                i++;
            }
        }
        
        return true;
    }
}
```
### Algorithm
- Create a `HashMap` to map the starting number of each piece to the piece itself.
- Iterate through the `pieces` array. For each `piece`, add an entry to the map: `map.put(piece[0], piece)`.
- Initialize an index `i = 0` to traverse `arr`.
- While `i` is less than `arr.length`:
  - Look for `arr[i]` as a key in the map. If it's not present, return `false`.
  - Retrieve the corresponding `piece` from the map.
  - Compare the elements of the `piece` with the elements of `arr` starting from index `i`.
  - If there is any mismatch, return `false`.
  - If they match, advance `i` by the length of the `piece`.
- If the loop completes, it means the entire `arr` has been successfully constructed. Return `true`.

# Solutions
### Java

```java
class Solution {
public
  boolean canFormArray(int[] arr, int[][] pieces) {
    for (int i = 0; i < arr.length;) {
      int k = 0;
      while (k < pieces.length && pieces[k][0] != arr[i]) {
        ++k;
      }
      if (k == pieces.length) {
        return false;
      }
      int j = 0;
      while (j < pieces[k].length && arr[i] == pieces[k][j]) {
        ++i;
        ++j;
      }
    }
    return true;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} arr * @param {number[][]} pieces * @return {boolean} */ var canFormArray =
  function (arr, pieces) {
    const d = new Map();
    for (const p of pieces) {
      d.set(p[0], p);
    }
    for (let i = 0; i < arr.length; ) {
      if (!d.has(arr[i])) {
        return false;
      }
      const p = d.get(arr[i]);
      for (const v of p) {
        if (arr[i++] != v) {
          return false;
        }
      }
    }
    return true;
  };

```

### CPP

```cpp
class Solution {
public:
  bool canFormArray(vector<int> &arr, vector<vector<int>> &pieces) {
    for (int i = 0; i < arr.size();) {
      int k = 0;
      while (k < pieces.size() && pieces[k][0] != arr[i]) {
        ++k;
      }
      if (k == pieces.size()) {
        return false;
      }
      int j = 0;
      while (j < pieces[k].size() && arr[i] == pieces[k][j]) {
        ++i;
        ++j;
      }
    }
    return true;
  }
};

```

### Python

```python
class Solution:
    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool: i = 0 while i < len(arr): k = 0 while k < len(pieces) and pieces[k][0] != arr[i]: k += 1 if k == len(pieces): return False j = 0 while j < len(pieces[k]) and arr[i] == pieces[k][j]: i, j = i + 1, j + 1 return True

```