Abstract / Summary

Find the largest number in a list that is at least twice as big as every other number.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

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 Solution class implements a method dominantIndex that receives a list of integers and returns the index of the largest element when it is at least twice as large as every other element. If this condition is not satisfied, the method returns -1. The implementation follows a concise functional style: it pairs each value with its original position, sorts the pairs in descending order, and then checks the dominance condition using the two highest values.

Key Steps

The algorithm can be broken down into three logical stages, each reflected in a distinct line of code.

Pairing values with their original indices

data = sorted([ (n, i) for i, n in enumerate(nums) ], reverse = True)

In this stage the comprehension iterates over nums with enumerate, producing a list of tuples where the first element is the number and the second element is its original index. The resulting list is then sorted in descending order based on the numeric value because the tuple’s first component is the number. The reverse = True flag ensures that the largest number appears at the front of the sorted list.

Selecting the candidate for dominance

The sorted list data now has its first element data[0] representing the maximum value together with its original position. The second element data[1] holds the second-largest value. No additional traversal is required; the sorting step guarantees that these two entries are the only ones needed for the final decision.

Evaluating the dominance condition and returning the result

return data[0][1] if data[0][0] >= 2 * data[1][0] else -1

Here the numeric part of the first tuple (data[0][0]) is compared against twice the numeric part of the second tuple (2 * data[1][0]). If the condition holds, the method returns the stored original index (data[0][1]). Otherwise, it returns -1 to indicate that no dominant element exists.

Edge Cases Handled

When the input list contains exactly two elements, the sorting step still produces a two-element data list, and the comparison between data[0][0] and 2 * data[1][0] works correctly.

If the list contains a single element, the list comprehension yields a single tuple. The sorting step leaves it unchanged, and the subsequent indexing of data[1][0] would raise an error in a naïve implementation. However, the problem specification for this method assumes at least two elements, and the code implicitly relies on that contract, thereby handling the single-element scenario by design.

When multiple elements share the same maximum value, the sorting order preserves the original index order for equal keys because Python’s sort is stable. Consequently, the first occurrence of the maximum value becomes data[0]. The dominance check then compares this maximum against the second-largest value, which may be equal to the maximum. In that case the condition fails and -1 is returned, correctly reflecting that no single element dominates the others.

The method also gracefully handles negative numbers. Since the comparison uses absolute multiplication (2 * data[1][0]), a negative maximum can dominate only if the second-largest value is more negative (i.e., has a smaller magnitude). The logic remains valid for any integer range supported by Python.

Performance Optimizations

The primary optimization resides in the use of Python’s built-in sorted function, which is implemented in C and provides a highly efficient Timsort algorithm. By constructing a list of (value, index) tuples and sorting it once, the code avoids multiple passes over the input array. The subsequent dominance check accesses only the first two entries of the sorted list, eliminating any need for additional iteration or manual maximum tracking.

Storing the original index alongside each value eliminates the need for a separate lookup after identifying the dominant element. This co-location of data ensures that the final result can be produced directly from the sorted structure without extra computation.

The list comprehension used to build the (value, index) pairs is executed in a single pass, leveraging Python’s iterator protocol for minimal overhead. Combining the comprehension with the sorting call also reduces temporary allocations, as the intermediate list is handed directly to sorted.

Overall, the design capitalizes on Python’s optimized standard library operations to achieve a compact and performant solution.

Imagine you have a long row of building blocks, and each block has a different number written on it. The goal is to see if the biggest block is at least twice as large as the second biggest block.

First, the code looks at every block to remember its number and exactly where it is sitting in the row. It acts like a helper who writes down the number and the spot for each one. Once it has that list, it sorts them all from the biggest number to the smallest one.

After the blocks are sorted, the code checks the two biggest ones. It looks at the very biggest block and checks if its number is at least two times the size of the next biggest block. If it is, the code tells you exactly where that biggest block was hiding in the original row. If the biggest block is not big enough compared to the runner-up, the code decides it is not the special winner and gives a signal that nothing was found.

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++	Java	Python							TS
	WalkCCC	C++	Java	Python
	leetcode.ca	C++	Java	Python	JS				Go		TS
	LeetcodeHelp	C++	Java	Python
	Progiez	C++	Java	Python
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai		Java
	Dijkstra-Edu		Java
	everthis				JS
	fartem							Ruby
	fengvyi	C++
	halfrost								Go
	haoel			Python
	JoshCrozier				JS
	keineahnung2345	C++
	Krazune									C
	lkwq007			Python
	lzl124631x	C++
	ruoru						Rust
	suxrobGM					C#
	varunu28		Java
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
Dijkstra-Edu	Java
everthis	JavaScript
fartem	Ruby
fengvyi	C++
halfrost	Go
haoel	Python
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C
lkwq007	Python
lzl124631x	C++
ruoru	Rust
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