1640. Check Array Formation Through Concatenation #

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 = [85], pieces = [[85]]
Output: true

Example 2:

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

Example 3:

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

Example 4:

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

Example 5:

Input: arr = [1,3,5,7], pieces = [[2,4,6,8]]
Output: false

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).

Problem Summary #

You are given an integer array arr, where every integer is distinct. You are also given an array pieces consisting of integer arrays, where the integers are also distinct. You need to concatenate the arrays in pieces in any order to form arr. However, you are not allowed to reorder the integers in each array pieces[i]. If the arrays in pieces can be concatenated to form arr, return true; otherwise, return false.

Solution Approach #

Easy problem. The problem guarantees that the elements in arr are unique, so we can use a map to store the index of each element for easy lookup. Traverse the pieces array, and for each one-dimensional array, determine whether the order of its elements is consistent with their relative order in the original arr. At this point, use the map for lookup. If the positions are consecutive one by one, then it is correct. If any order is not consecutive, or an element that does not exist in arr appears, return false.

Code #

package leetcode

func canFormArray(arr []int, pieces [][]int) bool {
	arrMap := map[int]int{}
	for i, v := range arr {
		arrMap[v] = i
	}
	for i := 0; i < len(pieces); i++ {
		order := -1
		for j := 0; j < len(pieces[i]); j++ {
			if _, ok := arrMap[pieces[i][j]]; !ok {
				return false
			}
			if order == -1 {
				order = arrMap[pieces[i][j]]
			} else {
				if arrMap[pieces[i][j]] == order+1 {
					order = arrMap[pieces[i][j]]
				} else {
					return false
				}
			}
		}
	}
	return true
}