Check Array Formation Through Concatenation

LeetCode 1640. Check Array Formation Through Concatenation is a nice warm-up problem that tests whether you can think in terms of hash maps for quick lookups. It looks like a simple matching exercise, but the way you organize the data makes all the difference between a clean solution and a messy one.

The problem

You are given an array arr of distinct integers. You are also given an array of integer arrays called pieces, where each sub-array contains distinct integers too, and the integers across all pieces are distinct.

Your goal: determine if you can concatenate the arrays in pieces in some order to form arr. You cannot reorder the elements within any individual piece.

For example, given arr = [15, 88, 1, 4, 2] and pieces = [[88], [1, 4, 2], [15]], the answer is True. You can arrange the pieces as [15] + [88] + [1, 4, 2] to get [15, 88, 1, 4, 2].

The brute force approach

The most obvious method: for each element in arr, search through all the pieces to find which one starts with that element. Then verify the rest of the piece matches the next elements in arr. If a piece has already been used, skip it.

This works, but for each position in arr you might scan through all pieces, giving you O(n * p) time where p is the number of pieces. Not terrible for small inputs, but there is a cleaner way.

The key insight

Since all integers are distinct, each element in arr can appear in at most one piece. That means the first element of each piece uniquely identifies which piece it is. You can build a hash map that maps each piece's first element to the entire piece. Then you just walk through arr, look up the current element in the map, and if a piece is found, verify the whole piece matches the next chunk of arr.

Step-by-step walkthrough

Let's trace through arr = [15, 88, 1, 4, 2] with pieces = [[88], [1, 4, 2], [15]].

The code

def can_form_array(arr, pieces):
    piece_map = {p[0]: p for p in pieces}

    i = 0
    while i < len(arr):
        if arr[i] not in piece_map:
            return False
        piece = piece_map[arr[i]]
        for val in piece:
            if i >= len(arr) or arr[i] != val:
                return False
            i += 1
    return True

The first line builds the hash map in one pass over pieces. Each piece's first element becomes the key, and the whole piece is the value.

Then we walk through arr with index i. At each position, we look up arr[i] in the map. If it is not there, no piece starts with this value, so formation is impossible. If it is there, we verify every element of the piece matches the corresponding elements in arr. If any element does not match, we return False. Otherwise, i advances past the entire piece, and we repeat for the next uncovered position.

Complexity analysis

Where n is the length of arr and p is the number of pieces.

The building blocks

1. Hash map for direct lookup

The core trick here is turning a search problem into a lookup problem. Instead of scanning the pieces list every time you need to find which piece starts with a given value, you precompute a dictionary keyed by the first element. This reduces each lookup from O(p) to O(1).

This is the same idea behind Two Sum (map values to indices), Group Anagrams (map sorted keys to groups), and countless other problems. Whenever you find yourself repeatedly searching a list for something, ask: can I precompute a map?

lookup = {item[0]: item for item in collection}

2. Sequential piece matching

Once you have the right piece, you need to verify it matches a contiguous chunk of the target array. This is a simple linear scan where you walk both the piece and arr in lockstep. If any element disagrees, you bail out immediately.

This pattern of "match a subsequence against a target" shows up in problems like merging sorted arrays, validating serialized data, and string matching.

Edge cases

Single-element pieces. If every piece has length 1, the problem reduces to checking whether arr is a permutation of the piece values. The hash map approach handles this without any special logic.

Single piece covering the entire array. If pieces contains just one array, you only need to check if that piece equals arr. The algorithm still works because it maps the first element, finds the piece, then verifies every element.

Element not in any piece. If arr contains a value that does not appear as the first element of any piece, the map lookup fails immediately and you return False. This catches the case where arr and pieces do not share the same elements.

Pieces that do not cover all of arr. If the total number of elements across all pieces is less than the length of arr, the while loop will eventually hit an element with no matching piece and return False.

From understanding to recall

Check Array Formation is a good example of a problem where the solution feels obvious once you see it, but the pattern it uses is worth drilling. The move from "search through a list" to "build a map and do O(1) lookups" is one of the most common optimizations in coding interviews. You will see it in easy problems like this one, and you will see it in hard problems where the map stores something more complex.

The gap between "I understand this" and "I can produce this under pressure" is real. Spaced repetition closes that gap. You practice building the hash map from scratch, matching pieces against the target array, and handling the edge cases. After a few cycles, the pattern fires automatically the moment you spot a problem that says "find something in a collection."

Related posts

• Group Anagrams - Another hash map grouping problem where the key function is the critical design choice
• Two Sum - The classic complement-lookup pattern using a hash map
• Contains Duplicate - The simplest "have I seen this before?" hash set problem