#2815

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Max Pair Sum in an Array

Find the maximum sum of two numbers in an array sharing the same largest digit using a hash-based scan efficiently.

Problem Statement

Given an integer array nums, identify the maximum sum of any pair of numbers where both numbers share the same largest digit. Each number's largest digit is determined by comparing all its digits.

For example, in nums = [112,131,411], the largest digits are [2,3,4], so no pair shares the same largest digit, and the result should be -1. Otherwise, return the maximum sum of such a pair.

Examples

Example 1

Input: nums = [112,131,411]

Output: -1

Each numbers largest digit in order is [2,3,4].

Example 2

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

Output: 5902

All the numbers have 6 as their largest digit, so the answer is 2536 + 3366 = 5902.

Example 3

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

Output: 88

Each number's largest digit in order is [5,7,7,4,4]. So we have only two possible pairs, 71 + 17 = 88 and 24 + 42 = 66.

Constraints

2 <= nums.length <= 100
1 <= nums[i] <= 104

Solution Approach

Map numbers by largest digit

Iterate through the array and compute the largest digit for each number. Store each number in a hash table where keys are the largest digits and values are lists of numbers.

Select top two per digit

For each key in the hash table, keep track of the two largest numbers with that largest digit. This ensures you can quickly compute the maximum pair sum without unnecessary comparisons.

Compute maximum pair sum

Scan through the hash table and calculate the sum of the top two numbers for each digit. Return the highest sum found, or -1 if no digit has two numbers.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) for scanning nums and computing largest digits, plus O(1) for maintaining top two per digit since digits range 1-9. Space complexity is O(n) for the hash table mapping digits to number lists.

What Interviewers Usually Probe

Check that your largest digit calculation handles multiple digits correctly.
Ask about how to efficiently track the two largest numbers per digit without sorting every time.
Clarify behavior when no two numbers share the same largest digit.

Common Pitfalls or Variants

Common pitfalls

Forgetting to update both largest and second largest numbers when scanning a digit's group.
Mixing up largest digit extraction, leading to incorrect pairings.
Returning zero or incorrect sum when no valid pair exists instead of -1.

Follow-up variants

Compute the maximum product of a pair sharing the same largest digit instead of the sum.
Return all pairs with the maximum sum that share the same largest digit.
Allow numbers with the same largest digit but from different arrays.

FAQ

How do I find the largest digit of a number for this problem?

Convert the number to a string or extract digits iteratively, then select the maximum digit.

What if no two numbers share the same largest digit?

Return -1, as the problem explicitly requires a valid pair with the same largest digit.

Can I sort the array first to simplify the solution?

Sorting is unnecessary; a hash map per largest digit is more efficient and avoids O(n log n) operations.

Does the array length constraint affect performance?

Since nums.length <= 100, the hash-based approach is fast and comfortably handles all allowed sizes.

Why use array scanning plus hash lookup pattern?

This pattern ensures efficient grouping and tracking of largest numbers per digit, avoiding redundant comparisons.

terminal

Solution

Solution 1: Enumeration

First, we initialize the answer variable $ans=-1$. Next, we directly enumerate all pairs $(nums[i], nums[j])$ where $i \lt j$, and calculate their sum $v=nums[i] + nums[j]$. If $v$ is greater than $ans$ and the largest digit of $nums[i]$ and $nums[j]$ are the same, then we update $ans$ with $v$.

1

2

3

4

5

6

7

8

9

class Solution:
    def maxSum(self, nums: List[int]) -> int:
        ans = -1
        for i, x in enumerate(nums):
            for y in nums[i + 1 :]:
                v = x + y
                if ans < v and max(str(x)) == max(str(y)):
                    ans = v
        return ans

Continue Practicing

#2813 maximum elegance of a k length subsequence #2808 minimum seconds to equalize a circular array #2830 maximize the profit as the salesman