#1640

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Check Array Formation Through Concatenation

Determine if an array can be formed by concatenating subarrays without reordering individual elements, using hash lookups efficiently.

array hash table

Problem Statement

You are given an array of distinct integers called arr and a collection of integer arrays called pieces, each containing distinct integers. Your goal is to determine if arr can be constructed by concatenating the arrays in pieces in any order, but the order of integers within each individual piece must remain unchanged.

Return true if it is possible to form the array arr by concatenating all pieces arrays without reordering their elements. Otherwise, return false. For example, given arr = [15,88] and pieces = [[88],[15]], the output is true because concatenating [15] then [88] reconstructs arr.

Examples

Example 1

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

Output: true

Concatenate [15] then [88]

Example 2

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

Output: false

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

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

Solution Approach

Create a hash map for pieces

Build a hash map mapping the first element of each piece to its corresponding subarray. This allows constant-time lookup to quickly determine if the next segment in arr matches a valid piece.

Scan the main array sequentially

Iterate through arr from left to right, using the hash map to find a matching piece starting at the current index. If a match exists, advance the index by the length of the matched piece. If no match is found, return false immediately.

Validate all segments

Continue scanning until the end of arr. If all elements are successfully matched to pieces in order without violating internal order, return true. Otherwise, return false, which covers cases where pieces cannot cover arr completely or in order.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) where n is the length of arr, since each element is scanned once and hash lookups are constant time. Space complexity is O(m) where m is the number of pieces, to store the hash map of first elements to subarrays.

What Interviewers Usually Probe

Checks if you recognize that distinct integers allow direct mapping without ambiguity.
Wants to see efficient scanning without nested loops over all pieces.
Observes if you handle unmatched segments and return false promptly.

Common Pitfalls or Variants

Common pitfalls

Attempting to reorder integers within a piece, which violates the problem constraints.
Scanning arr without using a hash map, resulting in unnecessary nested iteration and O(n*m) complexity.
Failing to handle cases where a piece starts correctly but does not fully match the segment in arr.

Follow-up variants

Allow pieces to contain duplicate integers, requiring frequency checks rather than direct mapping.
Use a version where arr may contain repeated elements and pieces may need multiple concatenations.
Require reconstruction using the minimal number of pieces concatenations to form arr.

FAQ

What is the main approach to solve Check Array Formation Through Concatenation?

Use a hash map to map the first element of each piece to its subarray, then scan arr sequentially to match pieces without reordering.

Can integers inside a piece be reordered to match arr?

No, the order of integers within each piece must remain exactly as given to satisfy the problem constraints.

What should I do if a segment in arr does not match any piece?

Immediately return false, since the array cannot be formed without using all segments correctly.

What is the time complexity of this solution?

Time complexity is O(n), where n is the length of arr, since each element is scanned once with constant-time hash lookups.

Does this pattern rely on elements being distinct?

Yes, distinct integers allow mapping each first element of a piece to a unique subarray, preventing ambiguity during concatenation.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

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

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

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

Continue Practicing

#1636 sort array by increasing frequency #1630 arithmetic subarrays #1656 design an ordered stream