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 or List . 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.

Description Hints 2 Solution Video 10:04

1640. Check Array Formation Through Concatenation

Q: 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.

Easy57.3% acceptance

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

Topics

Array Hash Table

Hints open one at a time

Hint 1

Note that the distinct part means that every position in the array belongs to only one piece

Hint 2

Note that you can get the piece every position belongs to naively

10:04

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[15,88]
[[88],[15]]

Input

[49,18,16]
[[16,18,49]]

Input

[91,4,64,78]
[[78],[4,64],[91]]

Your code is saved on this device.Solution