Skip to main content
Talentd

Check Array Formation Through Concatenation - Solution & Explanation

EasyArrayHash Table8 min read
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given an integer array arr and a list of subarrays pieces. The task is to determine whether arr can be formed by concatenating these pieces without reordering elements inside each piece. Pieces can appear in any order, but their internal sequence must stay intact.

Approach 1: Using a Dictionary to Map Start Elements (O(n) time, O(n) space)

The key observation: every piece starts with a unique value. Build a hash map where the key is the first element of each piece and the value is the piece itself. Then iterate through arr. Whenever you see a number, check if it exists in the map. If it does, retrieve the corresponding piece and verify each element matches the sequence in arr. Move the pointer forward by the length of that piece. If a number in arr does not start any piece, the formation is impossible.

This works because hash lookups run in constant time. Instead of scanning all pieces repeatedly, you directly jump to the correct piece using the first element as the identifier. The algorithm performs a single pass over arr with occasional sequential checks inside pieces, keeping the overall complexity linear. This approach heavily relies on hash table lookups and sequential traversal of the array.

Approach 2: Using Index Mapping and Sequential Checking (O(n) time, O(n) space)

Another way to structure the same idea is by building an index map from each value in arr to its position. Then iterate through each piece and verify that its elements appear consecutively in arr. For the first element of a piece, retrieve its index using the map. Then check the remaining elements to ensure they follow immediately after in arr. If any mismatch occurs or the sequence breaks, return false.

This approach focuses on validating each piece independently instead of scanning the main array. The index map enables constant-time position lookup, while sequential checks confirm the order constraint. The logic is straightforward and works well when you prefer validating pieces rather than walking through the main array.

Recommended for interviews: The dictionary-based scan is typically the expected solution. It demonstrates efficient use of a hash map and linear traversal of the input. Interviewers like it because it shows you recognized the unique starting element property and avoided unnecessary nested loops. Understanding both methods helps: the index-mapping variant shows the same idea from a different angle and reinforces how hash-based indexing simplifies sequence validation problems.

Approach 1: Using a Dictionary to Map Start Elements

In this approach, leverage a dictionary to map each number that starts a piece to the rest of the numbers in that piece. This allows us to quickly check if the numbers in arr can be sequentially matched with numbers in each piece in the correct order.

This Python solution creates a dictionary mapping that associates each starting number of a piece with the piece itself. It then iterates over the arr, extending the result list with the respective pieces. If any number is not found in the dictionary, it returns False. Finally, it checks if the constructed result list is equal to arr.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n) where n is the number of elements in arr. Space Complexity: O(n) for storing the result list.

Try this approach in the editor →

Approach 2: Using Index Mapping and Sequential Checking

This approach focuses on direct sequential checking by maintaining a mapping of each starting index in arr to its corresponding pieces index, allowing direct comparison with sections of the arr.

This C++ implementation utilizes an unordered map to associate the starting number of each piece with the piece itself. It iterates through arr, checking the mapping to see if the next piece matches the sequence from the current index.

Code

C++JavaScript

C++

JavaScript

Complexity

Time Complexity: O(n) where n is the number of elements in arr. Space Complexity: O(m) where m is the size of the pieces data structure.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using a Dictionary to Map Start Elements

Time Complexity: O(n) where n is the number of elements in arr. Space Complexity: O(n) for storing the result list.

Using Index Mapping and Sequential Checking

Time Complexity: O(n) where n is the number of elements in arr. Space Complexity: O(m) where m is the size of the pieces data structure.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dictionary Mapping by First ElementO(n)O(n)Best general solution. Efficient single pass with constant-time hash lookups.
Index Mapping and Sequential CheckO(n)O(n)Useful when validating each piece independently using array index positions.

Video Solution

Leetcode 1640. Check Array Formation Through Concatenation • Fraz • 2,988 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Check Array Formation Through Concatenation easy or hard?
This problem is classified as Easy. The challenge is recognizing that each piece has a unique starting value, which allows the use of a hash map for direct access. Once that observation is made, the implementation becomes a straightforward linear scan.
Check Array Formation Through Concatenation Python/Java solution
Python typically uses a dictionary mapping piece[0] to the full piece and iterates through arr with an index pointer. Java implementations use a HashMap<Integer, int[]> or List<Integer>. Both implementations achieve O(n) time complexity with O(n) additional space.
How to solve Check Array Formation Through Concatenation in O(n)?
Build a hash map where the key is the first element of each piece and the value is the piece itself. Traverse the array and use each element to check if it starts a piece. If it does, verify the following elements match that piece exactly. Because every lookup and comparison happens once, the total runtime remains linear.
What is the best approach for Check Array Formation Through Concatenation?
The hash map approach that maps the first element of each piece to the piece itself is the most efficient. Iterate through the array and use the current value to retrieve the correct piece in O(1) time. Then verify the sequence matches the array. This produces an overall O(n) time complexity with O(n) extra space.
Is Check Array Formation Through Concatenation asked at Google/Amazon/Meta?
Problems involving array reconstruction and hash map lookups appear frequently in technical interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the underlying technique of mapping values to sequences and validating order is common in interview question sets.
What data structure is used in Check Array Formation Through Concatenation?
A hash table (dictionary) is the primary data structure. It maps the first element of each piece to the corresponding subarray, allowing constant-time retrieval when scanning the main array. Arrays are also used for sequential comparison of elements.
What is the time complexity of Check Array Formation Through Concatenation?
The optimal solution runs in O(n) time, where n is the length of the array. Each element in arr is visited once, and hash map lookups for pieces take constant time. The extra space complexity is O(n) for storing the mapping of starting elements.

Ready to solve this problem?

Practice Check Array Formation Through Concatenation with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays