1640. Check Array Formation Through Concatenation
Problem Description
The problem presents a scenario where you have two arrays: arr
is a single list of distinct integers, and pieces
is a list of lists with each sublist also containing distinct integers. The goal is to determine if it is possible to form the arr
array by concatenating the subarrays in pieces
in any order. However, it is important to note that you cannot reorder the elements within the subarrays in pieces
. You must use the subarrays in pieces
as they are.
For example, if arr
= [1,2,3,4] and pieces
= [[2,3], [4], [1]], you could form arr
by concatenating [1], [2,3], and [4] in order. However, if pieces
were [[2,3], [1,4]], you could not form arr
because that would require reordering the integers within a piece, which is not allowed.
The task is to return true
if you can form arr
by such concatenations or false
otherwise.
Intuition
The intuition for solving this problem is to use a hash map to easily find the location of the subarrays in pieces
that can potentially be concatenated to match arr
. The first element of each subarray in pieces
can be used as a unique key in the hash map because we are given that all integers are distinct. This way, you can quickly look up the starting element of each piece to see if you can continue building arr
from the current position.
To arrive at the solution, we can follow these steps:
-
Create a hash map (
d
) where each key is the first integer of a subarray inpieces
, and the value is the subarray itself. -
Iterate over
arr
, and at each step:- Check if the current element exists in our hash map (
d
). If it doesnāt, it means there's a number inarr
that isn't the start of any piece, and thus we cannot formarr
fully. Returnfalse
. - If the present element is in
d
, fetch the corresponding subarray and check if the subsequent elements inarr
match this subarray exactly. If they donāt, returnfalse
because the ordering within a piece cannot be altered. - If they do match, increment the index (
i
) by the length of the piece, effectively 'skipping' over these elements inarr
.
- Check if the current element exists in our hash map (
-
If you reach the end of
arr
without returningfalse
, it means you've been able to build all ofarr
using thepieces
in the correct order, and hence returntrue
.
The solution demonstrates a greedy approach, building arr
incrementally from the start by mapping each element to a potential subarray from pieces
, ensuring the order within both arr
and pieces
remains unchanged.
Solution Approach
The solution approach to this problem uses a hash table (in Python, a dictionary) and array slicing.
-
Creating a hash table: A hash table (
d
) is created where for every subarray (p
) inpieces
, there's an entry with the key being the first element of the subarray and the value being the subarray itself. This allows us to quickly look up the piece that could potentially match a segment ofarr
starting from a given position.d = {p[0]: p for p in pieces}
This is very efficient because finding an item in a hash table has an average-case time complexity of O(1).
-
Iterating over the target array (
arr
): We then start walking througharr
from the first element, intending to find a match ind
.i, n = 0, len(arr) while i < n:
-
Checking existence in the hash table: For each element in
arr
, we first check whether this element is a key in our hash tabled
.if arr[i] not in d: return False
If it's not present, it means we cannot find a subarray in
pieces
to continue our concatenation, and the function should returnfalse
. -
Comparing subarrays: If we find the element in
d
, we fetch the corresponding subarray (p
). Then we slicearr
starting from the current indexi
up to the length of thep
and compare it with thep
.p = d[arr[i]] if arr[i : i + len(p)] != p: return False
If the sliced portion of
arr
and the subarrayp
do not match, it means the current segment cannot be formed with thepieces
provided, and we returnfalse
. -
Incrementing the index: If a match is found, we increment our current index (
i
) by the length of thep
to move past the part ofarr
we just confirmed.i += len(p)
-
Returning the result: After the loop, if we haven't returned
false
, it meansarr
has been successfully formed by concatenating the subarrays inpieces
, we returntrue
.return True
This algorithm's overall time complexity is O(n), where n is the number of elements in arr
, as we are iterating through each element once and hash map operations are O(1) on average. It's an efficient and effective way to solve the problem provided.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example:
Say we have arr
= [5, 6, 7] and pieces
= [[7], [5, 6]]. According to the problem, we can only concatenate subarrays from pieces
to form arr
and cannot change the order within each subarray.
Step 1: Creating a hash table
Firstly, we create a hash table where each key is the first element of the subarray from pieces
, and the value is the subarray itself.
d = {7: [7], 5: [5, 6]}
The hash table d
is now {5: [5, 6], 7: [7]}
.
Step 2: Iterating over the target array (arr
)
We aim to match elements in arr
to keys in d
:
i, n = 0, len(arr) # i - current index, n - length of arr
while i < n:
Step 3: Checking existence in the hash table
For each element arr[i]
, check if it is a key in d
.
- For
i = 0
,arr[i]
is5
. Since5
is a key ind
, we can continue to the next step. - If
arr[i]
were not ind
, for example,8
, we would returnFalse
.
Step 4: Comparing subarrays
Now, we need to check if the segment of arr
starting at index i
matches the subarray in d
.
- For
i = 0
,d[arr[i]]
is[5, 6]
. We comparearr[0:2]
([5, 6]
) with[5, 6]
, and they match.
If they didn't match or if arr
had fewer elements than the subarray p
, we would return False
.
Step 5: Incrementing the index
After finding a match, we skip over the matched part of arr
:
- Since the length of
[5, 6]
is2
, we incrementi
by 2:i += len([5, 6])
.
We then continue to the next iteration of the loop with i = 2
.
Step 6: Iterating continues
- Now
i = 2
andarr[i]
is7
. We look up7
in the hash table and get[7]
. - We compare
arr[2:3]
([7]
) with[7]
and they match.
Step 7: Returning the result
Having reached the end of arr
without returning False
, we can conclude that arr
can be formed by concatenating subarrays in pieces
. Therefore, the final result is True
.
By following these steps, we demonstrated that arr
can be formed from pieces
. This approach efficiently utilizes the hash table for quick lookups and array slicing for comparison, resulting in an efficient solution.
Solution Implementation
1class Solution:
2 def can_form_array(self, arr: List[int], pieces: List[List[int]]) -> bool:
3 # Create a dictionary that maps the first element of each piece to the piece itself
4 index_dict = {piece[0]: piece for piece in pieces}
5
6 i = 0 # Initialize a pointer to iterate through 'arr'
7 n = len(arr) # The length of 'arr'
8
9 # Loop through 'arr' using the pointer 'i'
10 while i < n:
11 # If the current element in 'arr' does not start any piece, return False
12 if arr[i] not in index_dict:
13 return False
14
15 # Retrieve the piece that starts with 'arr[i]'
16 current_piece = index_dict[arr[i]]
17
18 # Check if the next elements in 'arr' match this piece
19 if arr[i: i + len(current_piece)] != current_piece:
20 return False
21
22 # Move the pointer 'i' forward by the length of the matched piece
23 i += len(current_piece)
24
25 # If all pieces are matched without any issues, return True
26 return True
27
1class Solution {
2 public boolean canFormArray(int[] arr, int[][] pieces) {
3 // Create a hashmap to easily look up if a piece can be placed.
4 Map<Integer, int[]> piecesMap = new HashMap<>();
5
6 // Iterate over pieces and map the first element of each piece to the piece itself.
7 for (int[] piece : pieces) {
8 piecesMap.put(piece[0], piece);
9 }
10
11 // Use 'i' to traverse the arr array.
12 for (int i = 0; i < arr.length;) {
13 // Check if there is a starting piece for the current element in arr.
14 if (!piecesMap.containsKey(arr[i])) {
15 return false; // No piece starts with this element, return false.
16 }
17
18 // Get the piece that starts with arr[i].
19 for (int val : piecesMap.get(arr[i])) {
20 // Check if the element in arr matches the element in the piece.
21 if (arr[i++] != val) {
22 return false; // Element doesn't match, array can't be formed.
23 }
24 }
25 }
26
27 // All elements matched correctly, array can be formed.
28 return true;
29 }
30}
31
1#include <unordered_map>
2#include <vector>
3
4class Solution {
5public:
6 // Returns true if the arr can be formed by concatenating subarrays from pieces
7 bool canFormArray(std::vector<int>& arr, std::vector<std::vector<int>>& pieces) {
8 // Creating a hashmap to map the first element of each piece to its corresponding vector
9 std::unordered_map<int, std::vector<int>> piece_map;
10 for (auto& piece : pieces) {
11 piece_map[piece[0]] = piece;
12 }
13
14 // Iterate over the elements of arr
15 for (int i = 0; i < arr.size();) {
16 // If the current element of arr is not the first element of any piece, return false
17 if (piece_map.count(arr[i]) == 0) {
18 return false;
19 }
20 // Retrieve the piece that starts with the current element of arr
21 for (int& value : piece_map[arr[i]]) {
22 // Check if the current subsequence of arr matches the piece
23 // Increment index i for each match
24 if (arr[i++] != value) {
25 return false; // If there's a mismatch, return false
26 }
27 }
28 }
29
30 // If all elements of arr are matched with a piece correctly, return true
31 return true;
32 }
33};
34
1/**
2 * Checks if it's possible to form an array by concatenating subarrays in 'pieces' to match 'arr'.
3 * Each subarray in 'pieces' will appear at most once in 'arr'.
4 * The concatenation of all subarrays in 'pieces' is allowed to be in any order.
5 *
6 * @param {number[]} arr - The target array that we want to form.
7 * @param {number[][]} pieces - The subarrays that can be concatenated to form 'arr'.
8 * @returns {boolean} true if the 'arr' can be formed from 'pieces', otherwise false.
9 */
10function canFormArray(arr: number[], pieces: number[][]): boolean {
11 // The length of the target array.
12 const targetLength = arr.length;
13
14 let currentIndex = 0; // A pointer to track the current index in 'arr'
15
16 // While there are unprocessed elements in 'arr'
17 while (currentIndex < targetLength) {
18 // The current element we want to find in 'pieces'
19 const currentTargetValue = arr[currentIndex];
20
21 // Find the subarray in 'pieces' that starts with 'currentTargetValue'
22 const currentPiece = pieces.find(piece => piece[0] === currentTargetValue);
23
24 // If no such subarray exists, we cannot form 'arr'
25 if (!currentPiece) {
26 return false;
27 }
28
29 // Iterate through the elements of the found subarray
30 for (const item of currentPiece) {
31 // If any element doesn't match the corresponding element in 'arr', we cannot form 'arr'
32 if (item !== arr[currentIndex]) {
33 return false;
34 }
35 // Move the index in 'arr' forward
36 currentIndex++;
37 }
38 }
39
40 // If we processed all elements without issues, we can form 'arr'
41 return true;
42}
43
Time and Space Complexity
The given Python code defines a method canFormArray
which determines whether an array can be formed by concatenating the arrays in a given list pieces
. Let's analyze the time and space complexity of the code:
Time Complexity
- The construction of the dictionary
d
has a time complexity ofO(m)
, wherem
is the total number of elements inpieces
, since each of thek
sublists inpieces
is iterated over once. - The
while
loop iterates over each element ofarr
, which hasn
elements. Inside the loop, the check ifarr[i]
is ind
isO(1)
due to the hash map lookup, and the slice comparisonarr[i : i + len(p)] != p
isO(l)
wherel
is the length of the currentp
inpieces
. - In the worst case scenario, all
n
elements need to be checked, and we might have to compare against each of thek
pieces with an average length ofl
(assuming the pieces are approximately the same size; if they vary significantly, we'd consider an average size for a more accurate analysis).
Putting it all together, the overall time complexity is O(m + n * l)
, where m
is the total number of elements in pieces
, n
is the number of elements in arr
, and l
is the average length of the subarrays in pieces
.
Space Complexity
- The main extra space usage comes from the dictionary
d
, which contains at mostk
entries wherek
is the number of sublists inpieces
. The space complexity for storingd
isO(k)
. - There is also the space used by variable
p
which at maximum can hold a list of lengthl
. However, sincel
is at most the length ofarr
, this does not exceedO(n)
space. - Therefore, the space complexity of the code is
O(k + n)
.
Considering that the space required for d
is dependent on the number k
of sublists and each list is stored entirely, whereas the space required for p
and other local variables is negligible compared to the space for d
, we could simplify the space complexity to O(m)
because m
includes both the number of sublists and their individual lengths.
Learn more about how to find time and space complexity quickly using problem constraints.
How many ways can you arrange the three letters A, B and C?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!