---

1. Problem Summary

You are given:

• an integer array arr
• an array of integer arrays pieces

Your task is to determine whether arr can be formed by concatenating the arrays in pieces in any order, with these rules:

• You may rearrange the order of the subarrays in pieces
• Within each subarray, the order of elements cannot change
• All elements in arr must be used exactly once

Return:

true  if arr can be formed
false otherwise

Example interpretation:
Input:

arr = [85,1,2]
pieces = [[85],[1,2]]

We can concatenate [85] + [1,2] to form [85,1,2] → return true.

---

2. Key Insights

Each subarray in pieces must match starting from some index in arr

Because we cannot break or reorder elements inside a piece.

Values in arr are distinct (per problem constraints)

This allows mapping from value → piece index.

Matching must be sequential

Once we find a piece whose first value matches the current arr index, we check all values inside that piece.

If any mismatch occurs:

Return false immediately.

If all pieces match in proper alignment:

Return true.

---

3. Approach

Build a map for quick lookup and validate sequentially

Steps:

1. Build a hash map where: key = first element of each piece value = index of the piece
2. Iterate through arr using index i
3. For each value arr[i]:
   • if not present in map → return false
   • fetch the matching piece
   • verify each value in that piece matches arr sequentially
   • advance i appropriately
4. If entire arr matches successfully:
   return true

---

4. Time and Space Complexity

Time Complexity: O(N)

Where N = length of arr
Each element checked once.

Space Complexity: O(P)

Where P = number of pieces (for the map)

---

5. Java Solution

import java.util.*;

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;
    }
}

---

6. Dry Run Examples

Example 1

Input:

arr = [85,1,2]
pieces = [[85],[1,2]]

Map:

85 -> [85]
1  -> [1,2]

Scan arr:

• arr[0] = 85 → matches [85]
• arr[1] = 1 → matches [1,2] → check 1,2
  Result:

true

---

Example 2

Input:

arr = [15,88]
pieces = [[88],[15]]

Map:

88 -> [88]
15 -> [15]

Scan:

• arr[0] = 15 → matches [15]
• arr[1] = 88 → matches [88]

Output:

true

---

Example 3

Input:

arr = [49,18,16]
pieces = [[16,18,49]]

Map:

16 -> [16,18,49]

Scan:

• arr[0] = 49 → not in map → fail

Output:

false

---

Example 4

Input:

arr = [1,3,5,7]
pieces = [[2,4],[1],[3,5,7]]

Map:

2 → ...
1 → [1]
3 → [3,5,7]

Scan:

• arr[0] = 1 → matches [1]
• arr[1] = 3 → matches [3,5,7]
• all elements matched

Output:

true

---

Example 5 (order violation inside piece)

Input:

arr = [1,2,3]
pieces = [[1,3]]

Map:

1 → [1,3]

Scan:

• arr[0] = 1 → matches [1,3]
• next arr[1] = 2 but piece expects 3 → mismatch

Output:

false

---

7. Why This Solution Works

• Uses distinct value property for direct mapping
• Ensures piece sequences match exactly
• Validates full coverage of arr
• Efficient and linear time
• Eliminates guesswork of ordering

---

8. Common Mistakes

1. Attempting to permute pieces (unnecessary)
2. Allowing partial matches inside a piece
3. Misinterpreting problem and breaking pieces apart
4. Forgetting to advance index properly
5. Ignoring immediate mismatch cases