Abstract / Summary

You must combine two already ordered lists into one sorted array without using extra space.

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 55% (10+ million submissions).

Typical patterns to solve this problem:

• Array
• Sorting
• Two Pointers

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 Solution class with a single public method merge. The method receives two integer vectors, nums1 and nums2, together with their logical lengths m and n. Its purpose is to combine the elements of nums2 into nums1 and produce a sorted sequence that contains exactly m + n elements. The algorithm proceeds in three distinct phases: truncating the first vector to its logical size, prepending the second vector, and finally sorting the combined data.

Truncating the Destination Vector

The first operation adjusts the size of nums1 so that it reflects only the elements that are considered valid according to the parameter m. This is achieved with a call to resize:

nums1.resize(m);

By shrinking nums1 to m elements, any trailing placeholder values that may have been allocated for the merge are discarded. This step ensures that subsequent insertions operate on a clean container that contains exactly the intended portion of the original data.

Prepending the Source Vector

After the resize, the method inserts all elements of nums2 at the beginning of nums1. The insertion uses iterator ranges to specify the source and destination:

nums1.insert(nums1.begin(), nums2.begin(), nums2.end());

Placing the elements of nums2 at the front guarantees that the combined vector now holds n elements from nums2 followed by the original m elements from nums1. This ordering is irrelevant for the final result because the next step sorts the entire collection, but the choice of inserting at the front simplifies the logic by avoiding the need to compute an offset for the insertion point.

Sorting the Merged Collection

The final phase sorts the merged vector in non-decreasing order:

sort(nums1.begin(), nums1.end());

The standard library sort algorithm typically implements a hybrid introsort, which combines quicksort, heapsort, and insertion sort to achieve robust performance across a wide range of input patterns. By delegating the ordering to this highly tuned routine, the implementation benefits from the library’s internal optimizations without requiring custom comparison logic.

Edge Cases Handled

When m is zero, the resize operation reduces nums1 to an empty container. The subsequent insertion then simply copies all elements of nums2 into nums1. The sort call then orders the newly formed vector, which already contains only the elements of nums2.

When n is zero, the insertion range is empty, leaving nums1 unchanged after the resize. The sort operation runs on a vector that already contains exactly m elements, preserving the original order if it is already sorted, or rearranging it if necessary.

If both m and n are zero, the resize clears nums1, the insertion does nothing, and the sort operates on an empty range, which is a no-op. The method therefore gracefully handles empty inputs without raising exceptions or accessing invalid memory.

The code also tolerates cases where nums1 originally has a capacity larger than m. The resize call reduces the logical size without deallocating the underlying storage, allowing the subsequent insert to reuse the existing allocation when possible, which can reduce memory churn.

Performance Optimizations Observed

The use of resize before insertion eliminates the need to manage placeholder elements manually. By shrinking the vector to its logical size, the implementation avoids unnecessary comparisons or moves of unused slots during the sort phase.

The insert operation leverages the vector’s ability to shift elements in bulk. Inserting at the beginning requires moving the existing m elements to make room for the n new elements, but this movement is performed with a single contiguous memory operation, which is more efficient than repeated element-wise pushes.

Relying on the standard library’s sort brings in a highly optimized sorting routine that adapts to the data distribution. For already partially sorted data, the introsort may switch to insertion sort for small partitions, reducing overhead. For large, random data, it quickly falls back to quicksort-like partitioning, providing good average-case performance.

Overall, the algorithm minimizes explicit loops and manual element handling, delegating heavy lifting to well-optimized library functions. This approach reduces the chance of subtle performance pitfalls and benefits from years of tuning in the standard library implementation.

Imagine there are two baskets full of numbered toy blocks. The first basket is special because it starts with some empty spaces at the end, and the second basket is full of new blocks. The code works by first looking at the first basket and deciding exactly how many real blocks are inside. Then, it takes all the blocks from the second basket and pours them right into the front of the first basket so that everything gets mixed together in one pile. After all the blocks are in that single basket, the code rearranges them from the smallest number to the biggest number so that they are all nicely organized in a perfect line.

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

Time: loglinear
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++	Java	Python									TS
	WalkCCC	C++	Java	Python
	leetcode.ca	C++	Java	Python			Rust	JS	Go			PHP	TS
	LeetcodeHelp	C++	Java	Python
	MemoryLimitExceeded	C++		Python
	Progiez	C++	Java	Python
github	AdelDaniel										Dart
	aylei						Rust
	begeekmyfriend				C
	BigEggStudy					C#
	black-shadows	C++
	bujosa						Rust
	chandansgowda			Python
	charles-wangkai		Java
	chenyanzhe	C++
	Dijkstra-Edu		Java
	DimitrisJim				C
	everthis							JS
	fartem									Ruby
	FelixFan1122					C#
	fengvyi	C++
	fpdjsns	C++
	gaosq0604			Python
	gouthampradhan		Java
	halfrost								Go
	JoshCrozier							JS
	keineahnung2345	C++
	Krazune	C++
	lennylxx				C
	linouk23	C++
	lkwq007			Python
	luangong	C++
	MacJim				C
	muhammadfarhankt								Go
	pruthvikp			Python
	qiyuangong		Java
	ruoru						Rust
	shreymehul					C#
	sonugiri1043	C++
	suxrobGM					C#
	varunu28		Java
	vli02				C
	vthwang		Java
	wisdompeak	C++
	YuriSpiridonov			Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, PHP, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
AdelDaniel	Dart
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Rust
chandansgowda	Python
charles-wangkai	Java
chenyanzhe	C++
Dijkstra-Edu	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fengvyi	C++
fpdjsns	C++
gaosq0604	Python
gouthampradhan	Java
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C++
MacJim	C
muhammadfarhankt	Go
pruthvikp	Python
qiyuangong	Java
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
vli02	C
vthwang	Java
wisdompeak	C++
YuriSpiridonov	Python
zfang399	C++

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