Abstract / Summary

Check if a target array can be made by concatenating pieces from several given arrays in order.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 57% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Hash Table

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a recursive solution for determining whether a target array can be assembled by concatenating a selection of sub-arrays (pieces) without reordering the elements inside each piece. The method canFormArray receives the target list arr and a collection of candidate sub-lists pieces. It returns a Boolean indicating whether the target can be exactly reconstructed by a sequence of pieces, each used at most once, and respecting the original order of elements in arr.

Algorithm Description

The algorithm follows a depth-first search pattern. It first checks for the trivial case where the target array is empty; an empty target is considered successfully formed, so the function returns True. For a non-empty target, the function iterates over each piece in pieces. For each piece, it tests whether the piece matches the prefix of the current arr. The matching test is performed with a generator expression that compares each element of the piece with the corresponding element of arr. If a piece matches the prefix, the function recurses on the remainder of arr after removing the matched prefix, passing the same pieces collection unchanged. If none of the pieces match the current prefix, the function concludes that the target cannot be formed and returns False.

Base Case

if not arr:
    return True

When arr is empty, the recursion terminates successfully, indicating that all required elements have been matched by previously selected pieces.

Prefix Matching

if all(arr[i] == p[i] for i in range(len(p))):
    return self.canFormArray(arr[len(p):], pieces)

The all construct iterates over the indices of the current piece p. It ensures that every element of p aligns exactly with the corresponding element at the start of arr. If the condition holds, the function proceeds with a recursive call on the suffix of arr that begins after the matched segment.

Exhaustive Search Termination

return False

If the loop finishes without finding any piece that matches the current prefix, the function returns False, indicating that no valid concatenation exists for the remaining portion of arr.

Edge Cases Handled

The code explicitly handles the situation where the target array is empty, treating it as a successful formation. It also gracefully deals with pieces of varying lengths, including single-element pieces, by using the length of each piece in the matching loop. Because the matching test accesses arr[i] only up to len(p) - 1, the code avoids index errors even when a piece is longer than the remaining arr; in such a case the generator expression will raise an IndexError only if the piece length exceeds the length of arr. However, the all construct short-circuits on the first mismatch, effectively handling cases where a piece is longer than the remaining target segment without unnecessary comparisons.

Performance Optimizations Observed

The implementation leverages short-circuit evaluation in two places. First, the all generator stops as soon as a mismatched element is found, preventing a full scan of the piece when the prefix does not align early. Second, the recursive call is made immediately after a successful match, avoiding further iteration over the remaining pieces for the current recursion level. This early exit reduces the number of unnecessary comparisons in scenarios where the correct piece is found early in the list.

The use of recursion eliminates the need for explicit stack structures or auxiliary data containers, keeping the memory footprint minimal for each recursion depth. By passing the original pieces list unchanged into recursive calls, the algorithm avoids copying or modifying the collection, which conserves resources and avoids overhead associated with list duplication.

Imagine having a long train made of several colorful blocks hooked together in a specific order. You also have a box filled with smaller groups of these blocks. The goal is to see if you can take those smaller groups from the box and line them up exactly to rebuild the original long train.

The first part of the code checks if the train is already empty, which is like saying a train with no pieces is perfectly fine. Then, the code starts looking through the box of smaller groups. It picks up one small group and checks if those colored blocks match the very beginning of the long train. If the colors line up perfectly, the code takes those pieces off the front of the train and sets them aside. Then it starts all over again with the rest of the train to see if the remaining pieces also match the groups still left in the box. This keeps happening step by step until all the blocks are matched up. If the code tries every group and none of them fit the start of the train, then it knows it is impossible to build the train.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java					TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python	JS	Java	Go			Rust	TS
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	DimitrisJim							C
	everthis			JS
	fsq	C++
	halfrost					Go
	JoshCrozier			JS
	lkwq007		Python
	MacJim	C++
	suxrobGM						C#
	trung-hn		Python
	varunu28				Java
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
lkwq007	Python
MacJim	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality