Abstract / Summary

Find the median value from two ordered number lists without merging them.

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 47% (9+ million submissions).

Typical patterns to solve this problem:

• Array
• Binary Search
• Divide And Conquer

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 findMedianSortedArrays. The method receives two integer vectors that are already sorted individually. It produces a single double value representing the median of the combined multiset of elements from both vectors. The approach taken is to create a new container that holds all elements, sort the combined collection, and then extract the median based on the total count’s parity.

Key Steps

The algorithm proceeds through a clear sequence of operations, each reflected in a concise code fragment.

The first step creates a copy of the first input vector, establishing the base of the merged collection:

vector<int> both = nums1;

Next, the elements of the second vector are appended to the end of the copy. The insert call efficiently extends the container without the need for manual looping:

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

With all values now present in a single vector, the method sorts the combined data. The standard library sort algorithm is invoked, which internally selects an optimal hybrid sorting strategy for the given data size and type:

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

After sorting, the midpoint index is calculated by integer division of the total size. This index serves as the anchor for median extraction:

int mid = both.size() / 2;

The final stage distinguishes between even and odd total lengths. For an even count, the median is the arithmetic mean of the two central elements; for an odd count, it is simply the central element. The code expresses both cases directly:

if (both.size() % 2 == 0)
    return (double(both[mid-1]) + both[mid]) / 2;
else
    return both[mid];

Edge Cases Handled

The implementation gracefully manages scenarios where one or both input vectors are empty. By copying the first vector and then inserting the second, the resulting both vector correctly reflects the union of any combination of empty and non-empty inputs. The subsequent sorting step operates safely on an empty or singleton vector, as the standard sort algorithm is defined for zero or one element ranges.

When the combined size is even, the code accesses both[mid-1] and both[mid]. Because mid is derived from integer division, mid-1 is guaranteed to be a valid index for any even-sized collection with at least two elements. For an odd-sized collection, the direct return of both[mid] yields the exact middle element without additional computation.

The conversion to double in the even case ensures that the division yields a floating-point result, preserving fractional medians such as 2.5. In the odd case, the integer element is implicitly converted to double by the function’s return type, delivering a consistent numeric type for all outcomes.

Performance Optimizations

Although the algorithm follows a straightforward merge-and-sort strategy, it leverages several standard-library facilities that contribute to efficient execution. The initial copy of nums1 into both utilizes the vector copy constructor, which performs a bulk memory copy when possible, reducing overhead compared to element-wise insertion.

The insert operation appends an entire range in a single call. Internally, the vector may reallocate once to accommodate the additional elements, minimizing the number of memory allocations and copies required.

Sorting is delegated to std::sort, which typically implements introsort-a hybrid of quicksort, heapsort, and insertion sort. This choice adapts to the data’s characteristics, providing fast average-case performance while guarding against pathological worst-case scenarios without additional programmer effort.

Finally, the median extraction avoids any extra passes over the data. By computing the midpoint index once and using direct element access, the method eliminates unnecessary loops or conditional traversals, keeping the post-sort work to a constant amount of operations.

Imagine two collections of colorful building blocks, each already placed in a neat, straight line from smallest to biggest. The first part of this code takes all the blocks from the first line and adds them to the end of the second line, creating one long, mixed-up line. Since the new line is jumbled, the code uses a special trick to rearrange every block until they are all back in order, from the tiny ones at the start to the giant ones at the end.

Once all the blocks are lined up perfectly, the code looks for the very middle of the path. If the total number of blocks is an odd count, the middle block is exactly the answer. If there is an even total count of blocks, there will be two blocks sitting right in the center. In that case, the code grabs both of those center blocks and finds the halfway point between them to decide the final result.

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++	Python	Java											TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java	C#		JS	Go	C				Nim	PHP	TS
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	aylei					Rust
	begeekmyfriend								C
	BigEggStudy				C#
	black-shadows	C++
	bujosa					Rust
	chandansgowda		Python
	charles-wangkai			Java
	chenyanzhe	C++
	everthis						JS
	fartem									Ruby
	FelixFan1122				C#
	fengvyi	C++
	fpdjsns	C++
	fsq	C++
	gaosq0604		Python
	Garvit244		Python
	gouthampradhan			Java
	halfrost							Go
	haoel	C++
	JoshCrozier						JS
	keineahnung2345	C++
	lkwq007		Python
	luangong	C++
	MacJim	C++
	muhammadfarhankt							Go
	qiyuangong			Java
	ruoru					Rust
	Shamik07											Dart
	shreymehul				C#
	sonugiri1043	C++
	suxrobGM				C#
	varunu28			Java
	vli02								C
	wisdompeak	C++
	yuanliu666										Kotlin
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C, C++, C#, Go, Java, JavaScript, Nim, PHP, Python, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Rust
chandansgowda	Python
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fengvyi	C++
fpdjsns	C++
fsq	C++
gaosq0604	Python
Garvit244	Python
gouthampradhan	Java
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
luangong	C++
MacJim	C++
muhammadfarhankt	Go
qiyuangong	Java
ruoru	Rust
Shamik07	Dart
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
vli02	C
wisdompeak	C++
yuanliu666	Kotlin
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