LeetCode Problem 1640

Difficulty: 🟢 Easy
Topics: Array, Hash Table

Solution

LeetCode 1640 - Check Array Formation Through Concatenation

Problem Understanding

This problem gives us two inputs:

• arr, a one-dimensional array of distinct integers
• pieces, a collection of smaller integer arrays

The goal is to determine whether we can recreate arr by concatenating the arrays inside pieces in any order.

The important restriction is that we are not allowed to rearrange elements inside an individual piece. We may reorder entire pieces, but the order of numbers inside each piece must remain unchanged.

For example, if a piece is [4, 64], then those two numbers must appear consecutively and in exactly that order in the final constructed array. We cannot transform it into [64, 4].

The problem guarantees that:

• Every integer in arr is unique
• Every integer across all pieces is also unique
• The total number of integers across all pieces equals the size of arr

These guarantees are very important because they eliminate ambiguity. Since all numbers are distinct, each value in arr can belong to only one piece. That allows us to efficiently match sections of arr against the correct piece.

The constraints are very small:

• arr.length <= 100
• Total number of integers is at most 100

Even a slower solution would work comfortably within limits, but the problem naturally admits a clean linear-time solution using a hash map.

Several edge cases are important to consider:

• A piece may contain only one element
• A piece may appear to match partially but fail later because internal order differs
• The first element of some segment in arr may not exist as the beginning of any piece
• The pieces may already appear in the correct order, or they may need to be rearranged completely

Because integers are distinct, we never need to worry about duplicate matching or overlapping pieces.

Approaches

Brute Force Approach

A brute force strategy would try every possible ordering of pieces, concatenate them, and compare the resulting array with arr.

Suppose there are k pieces. We could generate all k! permutations of the pieces. For each permutation, we concatenate all arrays and check whether the result equals arr.

This approach is correct because it explores every possible valid ordering of the pieces. If any ordering reconstructs arr, we return true.

However, this solution becomes prohibitively expensive as the number of pieces grows. Factorial growth is extremely fast, making the approach impractical even for moderate input sizes.

Optimal Approach

The key observation is that each number is unique.

That means when we encounter a value in arr, there is at most one piece that could start with that value. Therefore, instead of trying permutations, we can directly locate the correct piece using a hash map.

We build a mapping:

• key = first number of a piece
• value = the entire piece

Then we scan through arr from left to right.

At each position:

1. Look up the current number in the hash map
2. Retrieve the matching piece
3. Verify that every element of the piece matches the corresponding section of arr

If any mismatch occurs, return false.

If we finish the scan successfully, return true.

This works because every piece must appear as a contiguous block inside arr, and distinct integers guarantee that the mapping is unambiguous.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(k! * n)	O(n)	Tries every permutation of pieces
Optimal	O(n)	O(n)	Uses a hash map to directly match pieces

Here:

• n is the total number of integers
• k is the number of pieces

Algorithm Walkthrough

1. Create a hash map where the key is the first integer of each piece, and the value is the entire piece.

This allows constant-time lookup of the correct piece when processing arr. 2. Initialize an index variable i = 0.

This index tracks our current position in arr. 3. While i is less than the length of arr, do the following:

• Check whether arr[i] exists as a key in the hash map.
• If it does not exist, return false immediately because no piece can begin with this number.

4. Retrieve the corresponding piece from the hash map.

Since integers are distinct, this is the only possible piece that could match here. 5. Compare every number in the piece with the corresponding numbers in arr.

For each element value in the piece:

• Verify that arr[i] == value
• If not, return false
• Otherwise increment i

6. Continue until all elements of arr have been processed.
7. If the entire array is matched successfully, return true.

Why it works

The algorithm relies on the uniqueness of integers.

Because every number appears exactly once across all pieces, the first number of a segment uniquely identifies which piece must appear there. Once we select that piece, its internal ordering cannot change, so the only valid action is to verify that the next elements in arr match exactly.

If every segment matches successfully, then concatenating the identified pieces reconstructs arr. If any mismatch occurs, no valid concatenation exists.

Python Solution

from typing import List

class Solution:
    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:
        piece_map = {}

        for piece in pieces:
            piece_map[piece[0]] = piece

        index = 0
        n = len(arr)

        while index < n:
            current = arr[index]

            if current not in piece_map:
                return False

            piece = piece_map[current]

            for value in piece:
                if index >= n or arr[index] != value:
                    return False
                index += 1

        return True

The implementation begins by constructing a dictionary called piece_map. Each key is the first element of a piece, and each value is the piece itself.

Next, the algorithm scans through arr using the variable index.

For every position in arr, we determine which piece must start there by looking up arr[index] in the dictionary. If no matching piece exists, the array cannot be formed.

Once the correct piece is found, we sequentially compare every element of the piece against the corresponding section of arr.

If a mismatch occurs at any point, the function immediately returns False.

If the entire array is consumed without mismatches, the function returns True.

Go Solution

func canFormArray(arr []int, pieces [][]int) bool {
	pieceMap := make(map[int][]int)

	for _, piece := range pieces {
		pieceMap[piece[0]] = piece
	}

	index := 0
	n := len(arr)

	for index < n {
		current := arr[index]

		piece, exists := pieceMap[current]
		if !exists {
			return false
		}

		for _, value := range piece {
			if index >= n || arr[index] != value {
				return false
			}
			index++
		}
	}

	return true
}

The Go implementation follows exactly the same logic as the Python solution.

A map[int][]int is used to associate each starting value with its corresponding piece. The algorithm then iterates through arr, retrieving and validating pieces one by one.

Go slices naturally handle variable-length pieces efficiently, so no additional data structure is needed.

Integer overflow is not a concern because all values are very small and no arithmetic operations are performed.

Worked Examples

Example 1

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

Step 1: Build Hash Map

Key	Value
88	[88]
15	[15]

Step 2: Traverse arr

Index	arr[index]	Matching Piece	Result
0	15	[15]	Match
1	88	[88]	Match

All elements match successfully.

Result: true

Example 2

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

Step 1: Build Hash Map

Key	Value
16	[16, 18, 49]

Step 2: Traverse arr

At index 0:

• arr[0] = 49
• No piece starts with 49

The algorithm immediately returns false.

Result: false

Example 3

arr = [91, 4, 64, 78]
pieces = [[78], [4, 64], [91]]

Step 1: Build Hash Map

Key	Value
78	[78]
4	[4, 64]
91	[91]

Step 2: Traverse arr

Index	arr[index]	Matching Piece	Result
0	91	[91]	Match
1	4	[4, 64]	Match
3	78	[78]	Match

All sections match correctly.

Result: true

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every element is visited once
Space	O(n)	Hash map stores all pieces

The algorithm processes each integer exactly once while validating pieces. Hash map lookups are constant time on average, so the total runtime is linear in the number of integers.

The additional space comes from storing the mapping between piece starting values and their arrays.

Test Cases

from typing import List

class Solution:
    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:
        piece_map = {}

        for piece in pieces:
            piece_map[piece[0]] = piece

        index = 0
        n = len(arr)

        while index < n:
            current = arr[index]

            if current not in piece_map:
                return False

            piece = piece_map[current]

            for value in piece:
                if index >= n or arr[index] != value:
                    return False
                index += 1

        return True

solution = Solution()

assert solution.canFormArray([15, 88], [[88], [15]]) is True
# pieces can be reordered

assert solution.canFormArray([49, 18, 16], [[16, 18, 49]]) is False
# internal order cannot change

assert solution.canFormArray([91, 4, 64, 78], [[78], [4, 64], [91]]) is True
# multiple pieces concatenate correctly

assert solution.canFormArray([1, 2, 3], [[2], [1, 3]]) is False
# partial mismatch inside a piece

assert solution.canFormArray([1], [[1]]) is True
# smallest valid input

assert solution.canFormArray([1, 2], [[1], [2]]) is True
# all single-element pieces

assert solution.canFormArray([1, 2], [[2], [1]]) is True
# piece order can change

assert solution.canFormArray([1, 2, 3], [[1, 2], [3]]) is True
# larger piece followed by smaller piece

assert solution.canFormArray([1, 2, 3], [[1], [2, 3]]) is True
# smaller piece followed by larger piece

assert solution.canFormArray([1, 2, 3], [[1, 3], [2]]) is False
# incorrect ordering inside piece

assert solution.canFormArray([85], [[85]]) is True
# single value edge case

Test	Why
[15,88], [[88],[15]]	Verifies piece reordering
[49,18,16], [[16,18,49]]	Verifies internal order restriction
[91,4,64,78], [[78],[4,64],[91]]	Tests normal successful concatenation
[1,2,3], [[2],[1,3]]	Detects partial mismatch
[1], [[1]]	Smallest valid input
[1,2], [[1],[2]]	All single-element pieces
[1,2], [[2],[1]]	Arbitrary piece ordering
[1,2,3], [[1,2],[3]]	Mixed piece lengths
[1,2,3], [[1],[2,3]]	Another mixed-length configuration
[1,2,3], [[1,3],[2]]	Invalid ordering within piece
[85], [[85]]	Single-value edge case

Edge Cases

Missing Starting Element

A very important edge case occurs when some value in arr does not appear as the first element of any piece.

For example:

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

When the algorithm starts at arr[0] = 1, it cannot find a piece beginning with 1. This immediately proves reconstruction is impossible.

The implementation handles this safely with:

if current not in piece_map:
    return False

Internal Ordering Mismatch

Another critical case happens when all numbers exist but the ordering inside a piece does not match arr.

Example:

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

The piece [1, 3] cannot fit into arr because after matching 1, the next value in arr is 2, not 3.

The implementation correctly detects this during element-by-element comparison.

Single Element Pieces

Some inputs contain only single-element pieces.

Example:

arr = [4, 5, 6]
pieces = [[6], [4], [5]]

This effectively reduces the problem to checking whether all values exist.

The algorithm naturally handles this because each piece comparison loop runs exactly once.

Single Piece Covering Entire Array

Another edge case occurs when one piece already contains the entire array.

Example:

arr = [7, 8, 9]
pieces = [[7, 8, 9]]

The algorithm correctly matches the entire piece in one pass and returns true.

This validates that the solution works for both many small pieces and one large piece.