LeetCode Problem 2815

Difficulty: 🟢 Easy
Topics: Array, Hash Table

Solution

LeetCode 2815 - Max Pair Sum in an Array

Problem Understanding

The problem gives us an array of integers nums. For every number, we can determine its largest digit. For example:

• 2536 has digits 2, 5, 3, 6, so its largest digit is 6
• 112 has digits 1, 1, 2, so its largest digit is 2
• 71 has digits 7, 1, so its largest digit is 7

We must find two numbers whose largest digit is the same. Among all such valid pairs, we want the pair with the largest possible sum.

If no two numbers share the same largest digit, then no valid pair exists, and we return -1.

The input consists of:

• An integer array nums
• Each element is between 1 and 10^4
• The array length is between 2 and 100

The output is:

• The maximum sum of a valid pair
• -1 if no valid pair exists

The constraints are quite small. With at most 100 numbers, even an O(n²) solution would be acceptable. However, there is a cleaner and more efficient approach that leverages the fact that the largest digit of any number can only be one of 0 through 9.

Several edge cases are worth noting:

• No valid pair exists, such as [112,131,411]
• Multiple numbers share the same largest digit, requiring us to find the two largest values among them
• Many numbers may belong to different groups
• Duplicate values are allowed and should be handled naturally
• A number may contain repeated digits, but only the maximum digit matters

Approaches

Brute Force

The most direct approach is to examine every possible pair of numbers.

For each pair (nums[i], nums[j]), compute the largest digit of both numbers. If the largest digits are equal, compute their sum and update the answer if this sum is larger than the current maximum.

Since there are O(n²) pairs and each largest-digit computation takes at most a few digit operations, this solution is straightforward and correct.

The drawback is that we repeatedly recompute the largest digit for the same numbers and examine all pairs even when a more direct grouping strategy is available.

Optimal Approach

The key observation is that the largest digit of a number can only be one of ten possible values: 0 through 9.

Instead of comparing every pair, we can group numbers by their largest digit.

For each largest-digit group, the maximum pair sum will always come from the two largest numbers in that group. Therefore, we only need to keep track of the largest number seen so far for each digit.

As we process each number:

1. Compute its largest digit.
2. Check whether we have already seen another number with the same largest digit.
3. If so, form a candidate pair using the current number and the largest previously seen number in that group.
4. Update the answer.
5. Update the stored maximum value for that largest-digit group.

This avoids checking all pairs explicitly and efficiently finds the best answer.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n² × d)	O(1)	Checks every pair, where d is the number of digits
Optimal	O(n × d)	O(1)	Groups by largest digit and tracks the largest value per group

Since nums[i] ≤ 10^4, each number contains at most 5 digits, so d is effectively constant.

Algorithm Walkthrough

1. Create a hash map that stores the largest number encountered for each possible largest digit.
2. Initialize the answer as -1. This value will remain unchanged if no valid pair exists.
3. Iterate through each number in nums.
4. For the current number, compute its largest digit by repeatedly extracting digits with modulo and division operations.
5. Check whether this largest digit already exists in the hash map.
6. If it does, then we have found another number with the same largest digit. Compute the pair sum using the current number and the largest previously stored number in that group.
7. Update the answer if this sum is larger than the current best answer.
8. Update the hash map entry for this largest digit with the larger of:

• the current stored value
• the current number

9. Continue until all numbers have been processed.
10. Return the final answer.

Why it works

For any largest-digit group, the optimal pair must consist of the two largest numbers in that group. While iterating, the hash map always stores the largest number encountered so far for each digit group. Whenever a new number arrives, pairing it with the largest previously seen number gives the best possible pair involving that new number. By considering every number once, we evaluate every candidate that could contribute to the global maximum pair sum, guaranteeing correctness.

Python Solution

from typing import List

class Solution:
    def maxSum(self, nums: List[int]) -> int:
        def largest_digit(num: int) -> int:
            maximum = 0
            while num:
                maximum = max(maximum, num % 10)
                num //= 10
            return maximum

        best_by_digit = {}
        answer = -1

        for num in nums:
            digit = largest_digit(num)

            if digit in best_by_digit:
                answer = max(answer, num + best_by_digit[digit])

            best_by_digit[digit] = max(
                best_by_digit.get(digit, 0),
                num
            )

        return answer

The helper function largest_digit() extracts each digit and keeps track of the maximum digit encountered.

The dictionary best_by_digit maps a largest digit to the largest number seen so far with that digit.

For every number, we first determine its largest digit. If another number with the same largest digit has already been seen, we compute a candidate pair sum using the stored maximum value for that group.

After evaluating the candidate pair, we update the stored maximum value if the current number is larger.

The variable answer continuously tracks the largest valid pair sum found during the traversal.

Go Solution

func maxSum(nums []int) int {
	largestDigit := func(num int) int {
		maxDigit := 0
		for num > 0 {
			digit := num % 10
			if digit > maxDigit {
				maxDigit = digit
			}
			num /= 10
		}
		return maxDigit
	}

	bestByDigit := make(map[int]int)
	answer := -1

	for _, num := range nums {
		digit := largestDigit(num)

		if best, exists := bestByDigit[digit]; exists {
			if num+best > answer {
				answer = num + best
			}
		}

		if current, exists := bestByDigit[digit]; !exists || num > current {
			bestByDigit[digit] = num
		}
	}

	return answer
}

The Go implementation follows exactly the same logic as the Python version. A map is used to store the largest number seen for each largest-digit group. Since the constraints are small and all values fit comfortably within Go's int type, there are no overflow concerns. The map lookup uses Go's comma-ok idiom to determine whether a group already exists.

Worked Examples

Example 1

Input: nums = [112,131,411]

Largest digits:

Number	Largest Digit
112	2
131	3
411	4

Processing:

Step	Number	Largest Digit	Map After Step	Answer
1	112	2	{2:112}	-1
2	131	3	{2:112, 3:131}	-1
3	411	4	{2:112, 3:131, 4:411}	-1

No two numbers share the same largest digit.

Result: -1

Example 2

Input: nums = [2536,1613,3366,162]

Largest digit for every number is 6.

Processing:

Step	Number	Candidate Sum	Map After Step	Answer
1	2536	N/A	{6:2536}	-1
2	1613	1613 + 2536 = 4149	{6:2536}	4149
3	3366	3366 + 2536 = 5902	{6:3366}	5902
4	162	162 + 3366 = 3528	{6:3366}	5902

Result: 5902

Example 3

Input: nums = [51,71,17,24,42]

Largest digits:

Number	Largest Digit
51	5
71	7
17	7
24	4
42	4

Processing:

Step	Number	Largest Digit	Candidate Sum	Answer
1	51	5	N/A	-1
2	71	7	N/A	-1
3	17	7	88	88
4	24	4	N/A	88
5	42	4	66	88

Result: 88

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n × d)	Each number is processed once, and finding its largest digit scans its digits
Space	O(1)	At most 10 largest-digit groups are stored

Because the largest digit can only be one of ten values, the hash map never contains more than ten entries. The digit count d is at most 5 because nums[i] ≤ 10^4, making the algorithm effectively linear in the size of the input array.

Test Cases

sol = Solution()

assert sol.maxSum([112, 131, 411]) == -1  # no valid pair
assert sol.maxSum([2536, 1613, 3366, 162]) == 5902  # example 2
assert sol.maxSum([51, 71, 17, 24, 42]) == 88  # example 3

assert sol.maxSum([11, 22]) == -1  # different largest digits
assert sol.maxSum([99, 89]) == 188  # same largest digit 9
assert sol.maxSum([9, 9]) == 18  # duplicate values
assert sol.maxSum([123, 321, 213]) == 444  # all in same group
assert sol.maxSum([10, 20, 30, 40]) == -1  # all different groups
assert sol.maxSum([98, 97, 96, 95]) == 195  # choose two largest
assert sol.maxSum([10000, 9999, 9000]) == 18999  # larger values
assert sol.maxSum([88, 18, 28, 38]) == 126  # multiple candidates
assert sol.maxSum([1, 2, 3, 4, 5, 5]) == 10  # smallest valid pair

Test Case Summary

Test	Why
[112,131,411]	No valid pair exists
[2536,1613,3366,162]	All numbers belong to one group
[51,71,17,24,42]	Multiple groups with different pair sums
[11,22]	Minimum-sized array with no pair
[99,89]	Single valid pair
[9,9]	Duplicate values
[123,321,213]	All numbers share largest digit 3
[10,20,30,40]	Distinct largest digits
[98,97,96,95]	Must choose the two largest values
[10000,9999,9000]	Values near upper constraint
[88,18,28,38]	Many candidates in one group
[1,2,3,4,5,5]	Small values with exactly one valid group

Edge Cases

No Valid Pair Exists

An array such as [112,131,411] has largest digits 2, 3, and 4. Since no group contains at least two numbers, there is no valid pair. The implementation correctly returns -1 because the answer variable is initialized to -1 and never updated.

More Than Two Numbers Share the Same Largest Digit

Consider [98,97,96,95]. Every number belongs to the largest-digit group 9. A common mistake is to use the first two numbers encountered. The optimal solution continuously tracks the largest number seen so far and evaluates every new number against it, ensuring that the final answer uses the two largest values, 98 and 97.

Duplicate Numbers

For input [9,9], both numbers have largest digit 9. Some implementations accidentally treat equal values as duplicates and ignore one of them. This solution processes every element independently, so the valid pair sum 18 is correctly computed.

Updating the Stored Maximum

Suppose the input is [50,80,70]. All numbers belong to the largest-digit group 8. After processing 50, the stored maximum is 50. After processing 80, the stored maximum becomes 80. When 70 is processed, it is paired with 80, producing the optimal sum 150. Continuously maintaining the largest value in each group is what guarantees the best pair is found.