Max Pair Sum in an Array

Difficulty: Easy | Acceptance: 60.60% | Paid: No Topics: Array, Hash Table

You are given a 0-indexed integer array nums. You are allowed to choose two different indices i and j of that array. The value of the pair (i, j) is defined as nums[i] + nums[j].

Return the maximum value of a pair of indices i and j such that i != j and the maximum digit of nums[i] and the maximum digit of nums[j] are equal. If no such pair exists, return -1.

• Examples
• Constraints
• Brute Force
• Sorting
• Hash Map

Examples

Input: nums = [51,71,17,24]
Output: 88
Explanation: 
i = 1 and j = 2, nums[i] = 71 and nums[j] = 17.
The maximum digit of 71 is 7 and the maximum digit of 17 is 7.
The sum of the pair (71, 17) is 88.

Input: nums = [1,2,3,4]
Output: -1
Explanation: No pair exists where the maximum digit of both numbers is equal.

Input: nums = [31,29,15,72,80]
Output: 152
Explanation:
i = 2 and j = 4, nums[i] = 15 and nums[j] = 80.
The maximum digit of 15 is 5 and the maximum digit of 80 is 8.
Wait, this example is incorrect based on problem logic. Let's stick to valid logic.
Correct Example 3 logic:
If nums = [84,91,18,59]
Max digits: 8, 9, 8, 9.
Pairs with 8: (84, 18) -> sum 102.
Pairs with 9: (91, 59) -> sum 150.
Max is 150.

Constraints

- 2 <= nums.length <= 100
- 1 <= nums[i] <= 10^4

Brute Force

Intuition Check every possible pair of indices in the array. For each pair, calculate the maximum digit of both numbers. If they are equal, update the maximum sum found so far.

Steps

• Initialize max_sum to -1.
• Iterate through the array with index i from 0 to n-1.
• Iterate through the array with index j from i+1 to n-1.
• For the pair (nums[i], nums[j]), find the maximum digit of each.
• If the maximum digits are equal, update max_sum with max(max_sum, nums[i] + nums[j]).
• Return max_sum.

class Solution:
    def maxSum(self, nums: list[int]) -> int:
        def max_digit(n):
            res = 0
            while n:
                res = max(res, n % 10)
                n //= 10
            return res
        
        n = len(nums)
        max_sum = -1
        for i in range(n):
            for j in range(i + 1, n):
                if max_digit(nums[i]) == max_digit(nums[j]):
                    max_sum = max(max_sum, nums[i] + nums[j])
        return max_sum

Complexity

• Time: O(n²) due to nested loops.
• Space: O(1) extra space.
• Notes: This will likely Time Limit Exceed (TLE) for large inputs (n up to 10⁵).

Sorting

Intuition If we sort the array in descending order, the largest numbers appear first. We can iterate through the sorted array and keep track of the largest number seen for each maximum digit. Since we process larger numbers first, the first time we encounter a digit group, we store that number. The second time we encounter the same digit, the sum with the stored number (which is the largest possible for that digit) will be the maximum sum for that group.

Steps

• Sort nums in descending order.
• Initialize a map/array best to store the largest number found for each max digit (0-9).
• Initialize max_sum to -1.
• Iterate through the sorted nums:
  • Calculate d = max digit of current number n.
  • If best[d] exists, calculate sum = n + best[d] and update max_sum.
  • If best[d] does not exist, set best[d] = n.
• Return max_sum.

class Solution:
    def maxSum(self, nums: list[int]) -> int:
        def max_digit(n):
            res = 0
            while n:
                res = max(res, n % 10)
                n //= 10
            return res
        
        nums.sort(reverse=True)
        best = {}
        max_sum = -1
        
        for n in nums:
            d = max_digit(n)
            if d in best:
                max_sum = max(max_sum, n + best[d])
            else:
                best[d] = n
                
        return max_sum

Complexity

• Time: O(n log n) due to sorting.
• Space: O(1) or O(n) depending on the sorting algorithm’s space complexity.
• Notes: Better than brute force, but we can do better with a Hash Map.

Hash Map

Intuition We only need to track the largest number seen so far for each possible maximum digit (0-9). As we iterate through the array, if we encounter a number whose max digit is already in our map, we can form a pair. We calculate the sum and update the global maximum. We also update the map to ensure it always holds the largest number for that digit seen so far.

Steps

• Initialize max_sum to -1.
• Initialize a map/array best of size 10 (for digits 0-9) with -1.
• Iterate through nums:
  • Calculate d = max digit of n.
  • If best[d] is not -1, it means we have seen a number with this max digit before. Update max_sum with max(max_sum, n + best[d]).
  • Update best[d] to max(best[d], n). This ensures best[d] holds the largest number encountered for this digit.
• Return max_sum.

class Solution:
    def maxSum(self, nums: list[int]) -> int:
        def max_digit(n):
            res = 0
            while n:
                res = max(res, n % 10)
                n //= 10
            return res
        
        max_sum = -1
        best = {}
        
        for n in nums:
            d = max_digit(n)
            if d in best:
                max_sum = max(max_sum, n + best[d])
            best[d] = max(best.get(d, 0), n)
            
        return max_sum

Complexity

• Time: O(n) since we iterate through the array once and max digit calculation is O(1) (max 10 digits).
• Space: O(1) because the map size is fixed at 10.
• Notes: This is the optimal solution.