Abstract / Summary

Given an integer list, find the largest possible product from any three numbers in it.

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 45% (800k+ submissions).

Typical patterns to solve this problem:

• Array
• Math
• 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 method maximumProduct. The method receives a list of integers and returns the maximum possible product of any three distinct elements from that list. The core strategy is to sort the input once and then evaluate the two candidate products that can yield the maximum result: the product of the three largest numbers and the product formed by the two smallest numbers (which may be negative) together with the largest number.

Key Steps

Sorting the Input

s = sorted(nums)

The method begins by creating a sorted copy of the input list. Sorting arranges the numbers in non-decreasing order, placing the smallest values at the beginning of the list and the largest values at the end. This ordering enables direct indexing of the extreme elements without additional scans.

Computing the Product of Two Smallest and the Largest

s[0] * s[1] * s[-1]

After sorting, the first two elements (s[0] and s[1]) represent the smallest values in the original list. If both are negative, their product becomes positive, and multiplying by the largest element (s[-1]) can produce a very large positive result. This expression captures the scenario where two large-magnitude negative numbers combine with a large positive number to yield the maximum product.

Computing the Product of the Three Largest

s[-3] * s[-2] * s[-1]

The last three elements of the sorted list (s[-3], s[-2], and s[-1]) are the three greatest values. Their product is the natural candidate for the maximum when all numbers are non-negative or when the largest positives dominate any contribution from negatives.

Selecting the Maximum of the Two Candidates

return max(s[0]*s[1]*s[-1], s[-3]*s[-2]*s[-1])

The final step uses the built-in max function to compare the two candidate products and return the larger one. This single comparison determines the correct answer for all possible distributions of signs and magnitudes in the input list.

Edge Cases Handled

When the input contains multiple negative numbers, the product of the two most negative values becomes positive. By explicitly considering s[0] * s[1] * s[-1], the algorithm correctly handles cases where the optimal triple consists of two negatives and one positive.

If the list includes zeros, the sorted order places zeros after any negative numbers and before positive numbers. The product calculations naturally incorporate zeros when they appear among the three largest or the two smallest, ensuring that a result of zero is returned when it is the maximum achievable value.

For inputs where all numbers are positive, the product of the three largest elements (s[-3] * s[-2] * s[-1]) dominates, and the algorithm selects it without interference from the negative-pair candidate.

When the list contains exactly three elements, sorting still produces a correctly ordered list, and both candidate expressions evaluate to the same product, guaranteeing the correct result.

Performance Optimizations

The implementation leverages Python’s highly optimized built-in sorted function, which performs an in-place Timsort with excellent real-world performance characteristics. By sorting once, the code avoids multiple passes over the data, reducing the overall number of element accesses.

All subsequent operations are simple index lookups and arithmetic on a constant number of elements (three multiplications and one comparison). This constant-time post-processing ensures that the dominant cost remains the initial sort, and no additional data structures are allocated beyond the sorted copy.

The use of the built-in max function provides a fast, C-level comparison, further minimizing overhead in the final selection step.

Overall, the solution achieves an efficient balance between readability and execution speed, relying on native language features to handle the heavy lifting.

Imagine you have a long row of number blocks lined up on the floor. First, you pick up all the blocks and put them in order from the smallest number on the left to the biggest number on the right. Once they are all sorted, you have two special ways to find a really big number by picking three blocks and multiplying them together. The first way is to take the two smallest blocks from the left side and multiply them by the very biggest block on the far right. Because two negative numbers multiplied together make a positive number, this can sometimes lead to a surprisingly huge result. The second way is to take the three biggest blocks from the very end of your line and multiply those together. You just check both of those groups and pick the one that gives you the biggest answer.

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