2815. Max Pair Sum in an Array

Problem

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.

Constraints:

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

Solution (Java)

class Solution {
    public int maxSum(int[] nums) {
        int ans = -1;
        Map<Integer,List<Integer>> ump = new HashMap<>();
        for(int i = 0; i < nums.length; ++i){
            int t = nums[i], maxDigit = 0;
            while(t != 0){ //evaluate max digit in the number
                maxDigit = Math.max(t%10, maxDigit);
                t = t/10;
            }
            if(!ump.containsKey(maxDigit)) ump.put(maxDigit, new ArrayList<>());
            ump.get(maxDigit).add(nums[i]); // add the number to the map
        }
        for(Map.Entry<Integer, List<Integer>> entry: ump.entrySet()){
            entry.getValue().sort(Comparator.reverseOrder()); //to find max two number in each max digit
            if(entry.getValue().size() >= 2) ans = Math.max(ans, entry.getValue().get(0) + entry.getValue().get(1)); //sum max two number and take max
        }
        return ans;
    }
}

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).