Abstract / Summary

Find the number that appears more than half the time in a list of integers.

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 66% (8+ million submissions).

Typical patterns to solve this problem:

• Array
• Counting
• Divide And Conquer
• Hash Table
• 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 solves the classic “majority element” problem by leveraging the C++ Standard Library algorithm nth_element. The method receives a mutable reference to a vector of integers, rearranges the elements such that the element at the middle position is the one that would appear there in a fully sorted array, and then returns that element. Because a majority element is defined as an element appearing more than half the time, it is guaranteed to occupy the middle index after partitioning, making this approach both concise and efficient.

Key Steps

Determining the middle index

auto mid = nums.size() / 2;

The code computes the integer division of the vector’s size by two, yielding the index that separates the lower half from the upper half of the collection. This index is central to the subsequent partitioning operation.

Partitioning with nth_element

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

nth_element rearranges the elements in the range [nums.begin(), nums.end()) so that the element positioned at nums.begin() + mid is exactly the element that would appear at that position in a fully sorted sequence. All elements before this position are guaranteed to be less than or equal to it, while all elements after are greater than or equal to it. The algorithm performs this rearrangement in-place, avoiding additional memory allocation.

Returning the candidate majority element

return nums[mid];

After the partitioning step, the element at the computed middle index is returned directly. If a majority element exists, it must be present at this position, satisfying the problem’s requirement.

Edge Cases Handled

When the input vector contains an odd number of elements, the middle index points to the exact central element, and nth_element ensures that this element reflects the median of the sorted order. For an even number of elements, integer division discards the fractional part, selecting the lower of the two central positions. In both scenarios, if a value appears more than half the time, it will occupy the selected middle position after partitioning, guaranteeing correct identification.

The algorithm also gracefully handles vectors where all elements are identical. In such cases, the partitioning step leaves the vector unchanged, and the returned element is trivially the majority element. Similarly, when the vector contains a diverse set of values but still includes a majority element, the partitioning isolates that element at the middle index without needing to examine the entire ordering.

Performance Optimizations

The use of nth_element is a deliberate optimization. Unlike a full sort, which would require O(n log n) operations, nth_element achieves the necessary positioning in linear average time, reducing the overall computational workload. Because the algorithm works directly on the input vector, it avoids allocating auxiliary containers, thereby minimizing memory overhead. The in-place nature of the operation also improves cache locality, as the data remains contiguous throughout the process. These characteristics collectively contribute to a solution that is both time-efficient and memory-conservative while maintaining clear and readable code.

Imagine you have a big bucket full of different colored blocks, and you want to find the color that shows up more than any other. Because there are so many blocks, it would take a long time to count every single one. Instead, it is much faster to mix them all up and look right at the middle of the pile.

The computer does this by taking the whole collection of numbers and shuffling them around until the ones that are smaller are on the left and the ones that are bigger are on the right. Once the numbers are organized this way, the secret to finding the most common one is to peek at the exact center of the line. Because the number you are looking for appears so often, it is guaranteed to be sitting right there in the middle spot after the rearranging is finished. It is just like finding a favorite toy in the center of a pile after tidying up.

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