Abstract / Summary

Find all elements that appear more than n over three times 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 57% (2+ million submissions).

Typical patterns to solve this problem:

• Array
• Counting
• 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 problem of finding all elements in an integer array that appear more than ⌊n/3⌋ times, where n is the length of the array. It follows a straightforward counting strategy using a hash-based frequency table, then filters the table based on the required occurrence threshold. The design is concise, leverages Python’s standard library for brevity, and handles a variety of input shapes without special-case code.

Key Steps

Frequency Accumulation

The algorithm begins by constructing a mapping from each distinct integer to its occurrence count. A defaultdict with an integer default value is employed so that each new key is automatically initialized to zero before being incremented.

freq = defaultdict(int)
for i in nums:
    freq[i] += 1

This loop processes the input list exactly once, updating the count for each element as it appears.

Threshold Computation

After the frequencies are known, the algorithm determines the minimum count an element must exceed to qualify as a majority element under the ⌊n/3⌋ rule. The integer division operator (//) yields the floor of the division, matching the problem’s definition.

threshold = len(nums) // 3

Result Extraction

The final phase iterates over the keys of the frequency table, selecting those whose count surpasses the previously computed threshold. Qualified elements are appended to a result list, which is then returned.

result = []
for i in freq:
    if freq[i] > threshold:
        result.append(i)
return result

Edge Cases Handled

The implementation naturally accommodates several edge conditions without additional branching:

• Empty Input - When nums is empty, len(nums) is zero, the threshold becomes zero, and the frequency table remains empty. The subsequent loop over freq yields no iterations, resulting in an empty list, which correctly represents the absence of majority elements.

• Single-Element Input - For a list containing one element, the threshold evaluates to zero (1 // 3 == 0). The sole element’s count is one, which is greater than zero, so it is included in the result. This aligns with the definition that any element in a single-element array appears more than ⌊1/3⌋ times.

• Two-Element Input - With two elements, the threshold is also zero (2 // 3 == 0). Both distinct elements, if different, will have a count of one, each exceeding the threshold, and both will be returned. If the two elements are identical, the single distinct value will be returned once, reflecting its count of two.

• All Elements Identical - When every entry in nums is the same value, its frequency equals n. Since n is always greater than n // 3 for n > 0, the algorithm returns a list containing that single value.

• Multiple Majority Elements - The algorithm does not assume uniqueness of the majority element. If more than one distinct value exceeds the threshold (possible when the array contains a mixture of three or more distinct values each appearing just over n/3 times), each qualifying value is added to the result list.

• Negative and Zero Values - The frequency table treats all integer keys uniformly, so negative numbers and zero are counted without special handling.

Performance Optimizations Observed

The code exhibits several implicit performance choices:

• Hash-Based Counting - By using a dictionary (defaultdict) for frequency storage, the algorithm achieves constant-time updates for each element, avoiding the need for nested loops or repeated scans.

• Single Pass for Counting - The counting loop processes each element exactly once, minimizing the number of read operations on the input list.

• Iterating Over Distinct Keys - The second loop iterates only over the unique elements present in the input, rather than over the entire list again. This reduces the number of iterations when the input contains many duplicate values.

• In-Place Threshold Calculation - Computing the threshold once before the filtering loop eliminates repeated division operations inside the loop body.

• Avoidance of Intermediate Structures - The algorithm builds only the essential frequency map and the final result list, without allocating additional temporary collections such as sorted copies or auxiliary arrays.

These choices collectively keep the runtime low and the memory footprint modest, especially for inputs with a high degree of repetition.

Imagine you have a big treasure box full of colorful plastic building blocks. You want to find out which colors appear the most often.

First, you pick up each block one by one and keep a little notebook. Every time you see a blue block, you put a tally mark next to the word blue in your notebook. You do the same for every red, green, or yellow block you find. By the time you finish looking at all the blocks, your notebook shows exactly how many of each color you have.

Next, you need to decide which colors are the winners. You count all the blocks in the pile and divide that number by three to set a special goal. If a color has more tally marks than that goal, it means that color is very popular. You take those winning colors and put them into a brand new box to keep. If a color does not have enough tally marks, it just stays behind in the big pile, and you ignore it.

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#			Java		Go	PHP
	LeetcodeHelp	C++	Python				Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python				Java
github	aylei				Rust
	begeekmyfriend							C
	BigEggStudy			C#
	black-shadows	C++
	chandansgowda		Python
	charles-wangkai						Java
	chenyanzhe	C++
	everthis					JS
	fengvyi	C++
	gaosq0604		Python
	halfrost								Go
	JoshCrozier					JS
	keineahnung2345	C++
	linouk23	C++
	lkwq007		Python
	MacJim	C++
	qiyuangong		Python
	ruoru				Rust
	shreymehul			C#
	sonugiri1043	C++
	suxrobGM			C#
	trung-hn		Python
	varunu28						Java
	vli02							C
	wisdompeak	C++
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, PHP, Python
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
fengvyi	C++
gaosq0604	Python
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lkwq007	Python
MacJim	C++
qiyuangong	Python
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
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