Abstract / Summary

Find the kth largest number in a list of integers without sorting the entire list.

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 69% (5+ million submissions).

Typical patterns to solve this problem:

• Array
• Divide And Conquer
• Heap (Priority Queue)
• Quickselect
• Sorting

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 findKthLargest. The method receives a mutable reference to a vector of integers and an integer k, and returns the k-th largest element in the collection. The core of the algorithm relies on the standard library function nth_element, which partially sorts the container such that the element at a specified position is the same as it would be in a fully sorted array, while all elements before it are less than or equal to it and all elements after it are greater than or equal to it. By selecting the appropriate index, the method extracts the desired order statistic directly.

Key Steps

The method consists of three distinct operations:

1. Compute the target index that corresponds to the k-th largest value when the vector is considered in ascending order.

   auto n = nums.size() - k;

2. Invoke nth_element to rearrange the vector so that the element at position n is the element that would appear there in a fully sorted sequence.

   nth_element(nums.begin(), nums.begin() + n, nums.end());

3. Return the element now residing at index n, which is the required k-th largest value.

   return nums[n];

Each step is expressed concisely, leveraging the expressive power of the C++ standard library.

Edge Cases

The algorithm implicitly handles several boundary conditions:

• When k equals 1, the target index becomes nums.size() - 1, positioning the call to nth_element such that the largest element is placed at the end of the vector. The final return yields the maximum value.
• When k equals the size of the vector, the target index becomes 0. In this scenario, nth_element ensures that the smallest element occupies the first position, and the method returns the minimum value, which is the k-th largest when k equals the total count.
• An empty vector is not a valid input for this method because k must be a positive integer less than or equal to the vector size. The code assumes that the caller respects this contract, and the calculation of n would otherwise produce an underflow, which is avoided by proper usage.
• Duplicate values are naturally accommodated because nth_element only guarantees partitioning relative to the pivot; equal elements may appear on either side of the pivot without affecting the correctness of the returned order statistic.

Performance Optimizations

The primary optimization stems from the use of nth_element instead of a full sort. nth_element operates in linear average time, rearranging only the necessary portion of the data to locate the desired element. This avoids the O(n log n) cost of a complete sort when only a single order statistic is required.

By computing the index as nums.size() - k, the method directly targets the position that corresponds to the k-th largest element in ascending order, eliminating any need for additional transformations or reverse traversals.

The algorithm works in-place, requiring no auxiliary containers. This reduces memory overhead and improves cache locality, as the vector is rearranged directly without copying elements to temporary storage.

Overall, the implementation delivers an efficient solution for retrieving the k-th largest element with minimal computational and memory resources.

Imagine you have a big messy pile of numbered blocks scattered across the floor. You want to pick out a specific one, like the third biggest block in the whole bunch.

The code starts by figuring out exactly where that special block should sit if you were to line everything up from smallest to largest. It uses a clever trick to rearrange the blocks so that the one you are looking for moves into its correct home. Instead of sorting the entire pile perfectly, it just makes sure the blocks smaller than your target are on one side and the blocks larger than your target are on the other side. Once the code finishes moving things around, the block sitting at that specific spot is exactly the one you wanted to find. It is like a magical game of musical chairs where the right block just lands right in front of you.

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

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