Check Array Formation Through Concatenation solution and explanation
9 more videos on this problem
Leetcode 1640. Check Array Formation Through ConcatenationFraz · 10:04 · 2K views
Check Array Formation Through Concatenation | LeetCode 1640 | C++, Java, PythonKnowledge Center · 16:26 · 1K views
Check Array Formation Through Concatenation | Live Coding with Explanation | Leetcode #1640Algorithms Made Easy · 7:52 · 1K views
Check Array Formation Through Concatenation | Leetcode 1640 | Live Coding sessionCoding Decoded · 11:58 · 1K views
Check Array Formation Through Concatenation | Leetcode 1640 | ArrayNaresh Gupta · 12:57 · 1K views
Check Array Formation Through Concatenation | Leetcode 1640 | leetcode solutionEasyLeetcode · 14:58 · 1K views
Leetcode - Check Array Formation Through Concatenation (Python)Timothy H Chang · 4:58 · 708 views
1640. Check Array Formation Through Concatenation (Leetcode Easy)Programming Live with Larry · 5:59 · 701 views
Daily Leetcode #276: Jan 01, 2021 - 1640. Check Array Formation Through ConcatenationProgramming Live with Larry · 16:24 · 428 views
Check Array Formation Through Concatenation | Leet code 1640 | Theory explained + Python codeSai Anish Malla · 9:30 · 386 views
The 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 = [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 <= 100sum(pieces[i].length) == arr.length1 <= pieces[i].length <= arr.length1 <= arr[i], pieces[i][j] <= 100- The integers in
arrare distinct. - The integers in
piecesare 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.
def canFormArray(arr, pieces):
mapping = {p[0]: p for p in pieces}
result = []
for number in arr:
if number in mapping:
result.extend(mapping[number])
else:
return False
return result == arrimport java.util.HashMap;
public boolean canFormArray(int[] arr, int[][] pieces) {
HashMap<Integer, int[]> map = new HashMap<>();
for (int[] piece : pieces) {
map.put(piece[0], piece);
}
int index = 0;
while (index < arr.length) {
if (!map.containsKey(arr[index])) {
return false;
}
int[] piece = map.get(arr[index]);
for (int num : piece) {
if (num != arr[index++]) {
return false;
}
}
}
return true;
}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.
Time Complexity: O(n) where n is the number of elements in arr. Space Complexity: O(n) for storing the result list.
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.
#include <unordered_map>
#include <vector>
using namespace std;
bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {
unordered_map<int, vector<int>> map;
for (auto& piece : pieces) {
map[piece[0]] = piece;
}
for (size_t i = 0; i < arr.size(); ) {
if (map.find(arr[i]) == map.end()) {
return false;
}
auto& piece = map[arr[i]];
for (int num : piece) {
if (num != arr[i++]) {
return false;
}
}
}
return true;
}function canFormArray(arr, pieces) {
const map = new Map();
for (const piece of pieces) {
map.set(piece[0], piece);
}
let i = 0;
while (i < arr.length) {
if (!map.has(arr[i])) {
return false;
}
const piece = map.get(arr[i]);
for (const num of piece) {
if (arr[i++] !== num) {
return false;
}
}
}
return true;
}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.
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.
Approach 3: Default Approach
function canFormArray(arr: number[], pieces: number[][]): boolean {
const n = arr.length;
let i = 0;
while (i < n) {
const target = arr[i];
const items = pieces.find(v => v[0] === target);
if (items == null) {
return false;
}
for (const item of items) {
if (item !== arr[i]) {
return false;
}
i++;
}
}
return true;
}func canFormArray(arr []int, pieces [][]int) bool {
for i := 0; i < len(arr); {
k := 0
for k < len(pieces) && pieces[k][0] != arr[i] {
k++
}
if k == len(pieces) {
return false
}
j := 0
for j < len(pieces[k]) && arr[i] == pieces[k][j] {
i, j = i+1, j+1
}
}
return true
}use std::collections::HashMap;
impl Solution {
pub fn can_form_array(arr: Vec<i32>, pieces: Vec<Vec<i32>>) -> bool {
let n = arr.len();
let mut map = HashMap::new();
for (i, v) in pieces.iter().enumerate() {
map.insert(v[0], i);
}
let mut i = 0;
while i < n {
match map.get(&arr[i]) {
None => {
return false;
}
Some(&j) => {
for &item in pieces[j].iter() {
if item != arr[i] {
return false;
}
i += 1;
}
}
}
}
true
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using a Dictionary to Map Start Elements | Time Complexity: O(n) where n is the number of elements in |
| Using Index Mapping and Sequential Checking | Time Complexity: O(n) where n is the number of elements in |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dictionary Mapping by First Element | O(n) | O(n) | Best general solution. Efficient single pass with constant-time hash lookups. |
| Index Mapping and Sequential Check | O(n) | O(n) | Useful when validating each piece independently using array index positions. |
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.