Check Array Formation Through Concatenation - Video Solutions

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.