Abstract / Summary

Given an array of integers, find the maximum sum obtained by pairing two distinct elements.

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 61% (100k+ submissions).

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 implementation computes the largest possible sum of two distinct numbers from the input list that share the same most-significant decimal digit. It proceeds in three logical phases: extracting the highest digit of each number, organizing numbers by that digit, and finally evaluating each group to obtain the maximum pair sum. The design avoids unnecessary work by limiting sorting to groups that can actually contribute to the answer.

Highest Digit Extraction

A small helper function isolates the most significant digit of a non-negative integer. It iteratively discards the least significant digit using integer division until the number is reduced to zero, while tracking the greatest digit encountered.

def maxDigit(n):
    result = 0
    while n > 0:
        result = max(result, n % 10)
        n //= 10
    return result

Edge handling: When n is zero the loop body never executes, leaving result at its initial value 0, which correctly represents the highest digit of zero. The function therefore works for the full range of non-negative integers.

Grouping by Highest Digit

A dictionary with keys 0 through 9 is created, each key mapping to an empty list. The input numbers are iterated once; each number is placed into the list that corresponds to its highest digit as returned by the helper.

high = { i: [] for i in range(10) }
for n in nums:
    high[maxDigit(n)].append(n)

Edge handling: Numbers that share the same highest digit accumulate in the same list, while digits that never appear retain empty lists. The structure gracefully accommodates an empty nums list, leaving all groups empty.

Selecting the Maximum Pair

The algorithm scans each digit group. Only groups containing at least two elements are considered, because a pair cannot be formed otherwise. For qualifying groups the list is sorted in ascending order, after which the two largest elements are accessed directly via negative indices. Their sum is compared with the current best result.

result = -1
for h in high:
    if len(high[h]) >= 2:
        high[h].sort()
        result = max(result, high[h][-2] + high[h][-1])
return result

Edge handling: If no digit group contains two or more numbers, the loop never updates result, and the function returns the sentinel value -1. This correctly signals the absence of a valid pair. The use of high[h][-2] and high[h][-1] is safe because the length check guarantees at least two elements.

Performance Optimizations

The code exhibits several deliberate choices that reduce runtime overhead:

• Single pass for grouping: Each input element is processed exactly once to determine its highest digit and placed into the appropriate bucket, avoiding repeated digit calculations.
• Conditional sorting: Sorting is performed only on groups that have the potential to produce a result (size ≥ 2). This prevents the cost of sorting many small or empty buckets.
• In-place list sort: The list.sort() method sorts the bucket without allocating a new list, conserving memory and leveraging the highly optimized Timsort algorithm.
• Dictionary comprehension for bucket initialization: The { i: [] for i in range(10) } expression creates all ten buckets in a single, efficient step.
• Use of built-in max: Both the digit extraction and the final comparison rely on Python’s native max, which is implemented in C and thus faster than a manual loop.

These choices collectively ensure that the algorithm scales well with the size of the input while keeping auxiliary work to a minimum.

Imagine there is a big collection of colorful blocks with numbers painted on them. The goal is to pick two blocks that have the same biggest digit inside them, like a three and a thirteen both have a three as their largest part, and add those two blocks together to get the biggest total possible.

First, a tiny machine looks at every single block one by one. It peeks at the numbers and finds the largest digit in each one. If a block has the number twenty-five, the machine sees that five is the biggest digit.

Then, there are ten little cubbies labeled zero through nine. As the machine looks at each block, it puts that block into the cubby that matches its biggest digit. If the biggest digit is five, the block goes into the five cubby.

Once all the blocks are tucked away in their cubbies, the machine checks each cubby to see if there are at least two blocks inside. If there are, it takes the two biggest ones from that cubby and adds them to see what total they make.

By doing this for every single cubby, the machine keeps track of the highest sum it has found so far. At the very end, it knows exactly which two blocks created the biggest number overall.

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		Java	C++		Python	TS
	WalkCCC		Java	C++		Python
	leetcode.ca		Java	C++	Go	Python	TS
	Progiez		Java	C++		Python
github	charles-wangkai		Java
	everthis	JS
	fsq			C++
	JoshCrozier	JS
	varunu28		Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
varunu28	Java

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