Check Array Formation Through Concatenation — Solution
Check Array Formation Through Concatenation solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Check Array Formation Through Concatenation is an easy coding problem on arrays and hash table, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
arr holds distinct integers, and pieces is a list of integer arrays whose values, taken all together, are also distinct. The pieces hold exactly as many numbers as arr.
You may place the pieces one after another in any order, but you may not reorder the numbers inside a piece. Return true if some order of the pieces concatenates to exactly arr.
Example 1
Input: arr = [12,40], pieces = [[40],[12]]
Output: true
Explanation: Place [12] then [40].
Example 2
Input: arr = [7,3,9], pieces = [[9,3,7]]
Output: false
Explanation: The single piece cannot be reversed.
Example 3
Input: arr = [5,21,8,30], pieces = [[30],[21,8],[5]]
Output: true
Constraints
1 <= pieces.length <= arr.length <= 100sum(pieces[i].length) == arr.length1 <= pieces[i].length <= arr.length1 <= arr[i], pieces[i][j] <= 100The integers in arr are distinctThe integers in pieces are distinct (across all pieces)
Hints for Check Array Formation Through Concatenation
Hint 1
Because all values are distinct, the first element of a piece can only go in one place.
Hint 2
Walk through
arrfrom the left; the value at the current position must start some piece.Hint 3
Index the pieces by their first element, then match that piece element by element and jump past it.
How to solve Check Array Formation Through Concatenation
Distinct values make the choice forced: whatever value sits at the current position of arr must be the first element of the next piece, and there is at most one piece that starts with it.
Approach
- Map each piece's first element to the piece.
- Set
i = 0. Whilei < n: look up the piece starting witharr[i]; if there is none, returnfalse. - Compare that piece with
arr[i..]element by element; on any mismatch returnfalse; otherwise advanceiby the piece's length. - Return
truewhenireachesn.
Why it works
At every step only one piece could be placed next, so the greedy walk is the only possible arrangement — if it fails, nothing succeeds. When it succeeds, it has consumed arr exactly, and since the pieces hold exactly n distinct values, every piece was used once.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- The order inside a piece is fixed — a piece cannot be reversed or rotated.
- A piece can be longer than what remains of
arr; check bounds while matching. - Values go up to 100, so a 101-slot array works as the index instead of a hash map.
Reference solution
Python
from typing import List
def canFormArray(arr: List[int], pieces: List[List[int]]) -> bool:
first = {p[0]: p for p in pieces}
i = 0
while i < len(arr):
p = first.get(arr[i])
if p is None or arr[i:i + len(p)] != p:
return False
i += len(p)
return TrueJava
public static boolean canFormArray(int[] arr, int[][] pieces) {
int[] first = new int[101];
Arrays.fill(first, -1);
for (int p = 0; p < pieces.length; p++) first[pieces[p][0]] = p;
int i = 0;
while (i < arr.length) {
int idx = first[arr[i]];
if (idx < 0) return false;
int[] piece = pieces[idx];
for (int j = 0; j < piece.length; j++) {
if (i + j >= arr.length || arr[i + j] != piece[j]) return false;
}
i += piece.length;
}
return true;
}C++
bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {
vector<int> first(101, -1);
for (int p = 0; p < (int)pieces.size(); p++) first[pieces[p][0]] = p;
int n = arr.size(), i = 0;
while (i < n) {
int idx = first[arr[i]];
if (idx < 0) return false;
const vector<int>& piece = pieces[idx];
for (int j = 0; j < (int)piece.size(); j++) {
if (i + j >= n || arr[i + j] != piece[j]) return false;
}
i += piece.size();
}
return true;
}JavaScript
var canFormArray = function(arr, pieces) {
var first = new Map();
for (var p = 0; p < pieces.length; p++) first.set(pieces[p][0], pieces[p]);
var i = 0;
while (i < arr.length) {
var piece = first.get(arr[i]);
if (piece === undefined) return false;
for (var j = 0; j < piece.length; j++) {
if (i + j >= arr.length || arr[i + j] !== piece[j]) return false;
}
i += piece.length;
}
return true;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets