Max Pair Sum in an Array

To find the maximum sum of a pair of numbers from the given array where the maximum digit in both numbers are equal, you can follow these steps:

  1. Create a dictionary where the key is the maximum digit of a number and the value is a list of numbers with that maximum digit.
  2. Iterate through the given array, finding the maximum digit of each number, and add the number to the appropriate list in the dictionary.
  3. Iterate through the values of the dictionary, finding the maximum sum of pairs in each list.
  4. Return the global maximum sum or -1 if no such pair exists.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def maxSum(self, nums: List[int]) -> int:
        max_digit_dict = {}

        # Group numbers by their maximum digit
        for num in nums:
            max_digit = max(int(digit) for digit in str(num))
            if max_digit not in max_digit_dict:
                max_digit_dict[max_digit] = []
            max_digit_dict[max_digit].append(num)

        max_sum = -1

        # Iterate through the groups to find the maximum sum of pairs with the same maximum digit
        for numbers in max_digit_dict.values():
            if len(numbers) > 1:
                sorted_numbers = sorted(numbers, reverse=True)
                pair_sum = sorted_numbers[0] + sorted_numbers[1]
                max_sum = max(max_sum, pair_sum)

        return max_sum

This code groups the numbers by their maximum digit and then finds the maximum sum of pairs with the same maximum digit, returning the result.