Abstract / Summary

Given a list of citations, find the highest number where at least that many papers have citations equal to or greater than that number.

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 42% (2+ million submissions).

Typical patterns to solve this problem:

• Array
• Counting Sort
• 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 computes the h-index for a researcher given a list of citation counts. The algorithm follows a straightforward approach: it first orders the citation numbers in descending order, then iterates through the sorted list while a simple condition holds, and finally returns the count of papers that satisfy the h-index definition. The code is concise, uses only built-in list operations, and avoids any external dependencies.

Key Steps

The first operation prepares the data for linear scanning by sorting it in non-increasing order.

citations.sort(reverse = True)

Sorting places the most-cited papers at the beginning of the list, which aligns the index of each element with the potential h-index value. After sorting, the algorithm initializes a counter that will represent the current candidate for the h-index.

h = 0

A while loop then walks through the sorted list. The loop condition checks two things: that the counter has not exceeded the length of the list, and that the citation count at the current position is at least the candidate h-index plus one.

while h < len(citations) and citations[h] >= h + 1:
    h += 1

Inside the loop the counter is incremented, effectively advancing to the next paper and raising the candidate h-index. When the loop terminates, the counter holds the maximum value that satisfies the h-index condition, and it is returned.

return h

Edge Cases Handled

The loop condition h < len(citations) guarantees that the algorithm never attempts to access an index beyond the bounds of the list, so an empty citation list is safely processed. In that scenario the initial value of h remains zero and the method returns zero, which correctly reflects that no papers have citations.

When all citation counts are zero, the sorted list still contains zeros, and the condition citations[h] >= h + 1 fails immediately because 0 >= 1 is false. The loop does not execute, leaving h at zero, which matches the definition of an h-index of zero.

If the citation counts are strictly decreasing and each value is at least the position index plus one, the loop will iterate through the entire list. For example, with citations [5,4,3,2,1] the condition holds for each element, and h ends up equal to the length of the list, yielding an h-index equal to the total number of papers.

When there are duplicate citation values, the sorted order still groups equal values together, and the condition correctly evaluates each position independently. For instance, with citations [3,3,3,0] the loop stops after the third element because the fourth element fails the condition, resulting in an h-index of three, which is accurate.

Performance Optimizations

The algorithm leverages the built-in list.sort method with the reverse=True flag, which is implemented in C and provides an efficient in-place sort. By sorting in descending order, the subsequent linear scan can stop as soon as the h-index condition fails, avoiding unnecessary comparisons for the tail of the list.

The use of a single integer counter h eliminates the need for auxiliary data structures such as auxiliary arrays or hash maps. This minimal memory footprint ensures that the method operates with constant extra space beyond the input list.

The loop condition combines the boundary check and the citation comparison in a single logical expression, allowing the interpreter to short-circuit evaluation. As soon as h reaches the length of the list, the second part of the condition is not evaluated, preventing an out-of-range access.

Because the algorithm stops early when the condition fails, the average number of iterations can be significantly lower than the list length for skewed citation distributions, providing a practical speed advantage on typical data sets.

Imagine a bookshelf full of storybooks, and each book has a little number written on the cover to show how many times other friends have borrowed it. To find out how popular these books are, start by shuffling them around so the stories with the most borrowed counts are at the very front of the shelf.

Think of a tiny robot that starts at the first book and walks down the line. For every book the robot passes, it adds one to its counter. The robot keeps walking as long as the book it is looking at has been borrowed at least as many times as the number of books the robot has already counted. It is like the robot is checking if there is a group of books that all have a matching level of popularity. Once the robot finds a book that is not quite popular enough to keep the pattern going, it stops walking and remembers how many steps it took.

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	Rust				Go	TS
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	aylei				Rust
	BigEggStudy						C#
	black-shadows	C++
	charles-wangkai			Java
	chenyanzhe	C++
	everthis					JS
	fengvyi	C++
	gouthampradhan			Java
	halfrost								Go
	haoel	C++
	JoshCrozier					JS
	keineahnung2345	C++
	lennylxx							C
	linouk23	C++
	lkwq007		Python
	MacJim	C++
	qiyuangong		Python
	ruoru				Rust
	suxrobGM						C#
	trung-hn		Python
	varunu28			Java
	vli02							C
	wisdompeak	C++
	YuriSpiridonov		Python
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
aylei	Rust
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
fengvyi	C++
gouthampradhan	Java
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lennylxx	C
linouk23	C++
lkwq007	Python
MacJim	C++
qiyuangong	Python
ruoru	Rust
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
wisdompeak	C++
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