2815. Max Pair Sum in an Array Easy

You are given a 0-indexed integer array nums. You have to find the maximum sum of a pair of numbers from nums such that the maximum digit in both numbers are equal.

Return the maximum sum or -1 if no such pair exists.

Example 1:
Input: nums = [51,71,17,24,42]
Output: 88
Explanation:
For i = 1 and j = 2, nums[i] and nums[j] have equal maximum digits with a pair sum of 71 + 17 = 88.
For i = 3 and j = 4, nums[i] and nums[j] have equal maximum digits with a pair sum of 24 + 42 = 66.
It can be shown that there are no other pairs with equal maximum digits, so the answer is 88.

Example 2:
Input: nums = [1,2,3,4]
Output: -1
Explanation: No pair exists in nums with equal maximum digits.

Approach

Input: An array nums

Output: Find the maximum sum of a pair of numbers where both numbers share the same maximum digit. Return the maximum sum.

This is an Array Sorting + Hash Table problem.

We can sort the array first before iterating. We also need a hash table to record the index of the previously seen maximum digit.

During each iteration, check the hash table to see if the same maximum digit has appeared before. If found, calculate the pair sum.

Because it's a sorted array, any matching number found later will necessarily be larger, so we can directly overwrite the index in the hash table with the current one.

Implementation

python

class Solution:
    def maxSum(self, nums: List[int]) -> int:
        # Sort the input array in ascending order for easier processing
        nums.sort()

        # Initialize dictionary to store the index corresponding to each maximum digit
        cache = {}
        # Initialize max sum to -1 (indicating no valid pair found yet)
        maxVal = -1

        # Iterate over the array
        for i in range(len(nums)):
            # Initialize the maximum digit of the current number
            maxD = 0
            # Get the current number
            num = nums[i]

            # Calculate the maximum digit of the current number
            while num:
                maxD = max(maxD, num % 10)  # Compare the last digit with the current maximum digit
                num = num // 10  # Remove the last digit
            
            # If the current max digit is already in the cache, try to update max sum
            if maxD in cache:
                maxVal = max(nums[cache[maxD]] + nums[i], maxVal)
            
            # Update cache, recording the index of the current maximum digit
            cache[maxD] = i
        
        # Return the maximum sum, returning -1 if no valid pair found
        return maxVal

javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSum = function(nums) {
    nums.sort((a, b) => a - b);

    let maxVal = -1;
    const cache = {};

    for (let i = 0; i < nums.length; i++) {
        let num = nums[i];

        let maxD = 0;
        while (num > 0) {
            maxD = Math.max(maxD, num % 10);
            num = Math.floor(num / 10);
        }

        if (maxD in cache) {
            maxVal = Math.max(maxVal, nums[cache[maxD]] + nums[i]);
        }

        cache[maxD] = i;
    }

    return maxVal;
};

Complexity Analysis

• Time Complexity: O(n log n)
• Space Complexity: O(1) space since max digit cache only has 10 keys (0-9)

Links

2815. Max Pair Sum in an Array (English)2815. 数组中的最大数对和 (Chinese)