Naive Solution

A brute-force approach involves iterating through each pair of numbers in the input array nums, finding the largest digit in each number, and checking if the largest digits are equal. If they are, the sum of the pair is calculated, and the maximum sum is updated accordingly. If no such pair exists, return -1.

Example

Given nums = [51, 71, 17, 24, 42]

1. Iterate through all possible pairs:
   • (51, 71): Largest digits are 5 and 7, respectively. Not equal.
   • (51, 17): Largest digits are 5 and 7, respectively. Not equal.
   • (51, 24): Largest digits are 5 and 4, respectively. Not equal.
   • (51, 42): Largest digits are 5 and 4, respectively. Not equal.
   • (71, 17): Largest digits are 7 and 7, respectively. Equal. Sum = 71 + 17 = 88.
   • (71, 24): Largest digits are 7 and 4, respectively. Not equal.
   • (71, 42): Largest digits are 7 and 4, respectively. Not equal.
   • (17, 24): Largest digits are 7 and 4, respectively. Not equal.
   • (17, 42): Largest digits are 7 and 4, respectively. Not equal.
   • (24, 42): Largest digits are 4 and 4, respectively. Equal. Sum = 24 + 42 = 66.
2. The maximum sum is max(88, 66) = 88.

Code

import java.util.Arrays;

class Solution {
    public int maxSum(int[] nums) {
        int maxSum = -1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (findLargestDigit(nums[i]) == findLargestDigit(nums[j])) {
                    maxSum = Math.max(maxSum, nums[i] + nums[j]);
                }
            }
        }
        return maxSum;
    }

    private int findLargestDigit(int num) {
        int largestDigit = 0;
        String numStr = String.valueOf(num);
        for (int i = 0; i < numStr.length(); i++) {
            int digit = Character.getNumericValue(numStr.charAt(i));
            largestDigit = Math.max(largestDigit, digit);
        }
        return largestDigit;
    }
}

Time Complexity

O(n^2), where n is the length of the input array nums. This is because we iterate through each possible pair of numbers.

Space Complexity

O(1), as we only use a constant amount of extra space.

Optimal Solution

An optimized approach involves using a hash map (or an array since digits range from 0-9) to store the maximum number encountered so far for each largest digit. Then, iterate through the array once. For each number, find its largest digit. Check if the largest digit is already present in the hash map. If it is, compute the sum of the current number and the number stored in the hash map for the same largest digit. Update maxSum if the sum is larger than the current maxSum. Update the hash map with the larger value between the current number and what already exists.

Example

Given nums = [51, 71, 17, 24, 42]

1. Initialize maxSum to -1 and a hash map largestDigitMap.
2. Iterate through nums:
   • nums[0] = 51: Largest digit is 5. largestDigitMap is empty. Store 51 in largestDigitMap with key 5.
   • nums[1] = 71: Largest digit is 7. largestDigitMap does not contain 7. Store 71 in largestDigitMap with key 7.
   • nums[2] = 17: Largest digit is 7. largestDigitMap contains 7 (value 71). Sum = 71 + 17 = 88. maxSum = 88. Update largestDigitMap with max(71, 17) = 71 for key 7.
   • nums[3] = 24: Largest digit is 4. largestDigitMap does not contain 4. Store 24 in largestDigitMap with key 4.
   • nums[4] = 42: Largest digit is 4. largestDigitMap contains 4 (value 24). Sum = 24 + 42 = 66. maxSum = max(88, 66) = 88. Update largestDigitMap with max(24, 42) = 42 for key 4.
3. Return maxSum = 88.

Code

import java.util.Arrays;

class Solution {
    public int maxSum(int[] nums) {
        int maxSum = -1;
        int[] largestDigitMap = new int[10];
        Arrays.fill(largestDigitMap, -1);

        for (int num : nums) {
            int largestDigit = findLargestDigit(num);
            if (largestDigitMap[largestDigit] != -1) {
                maxSum = Math.max(maxSum, largestDigitMap[largestDigit] + num);
            }
            largestDigitMap[largestDigit] = Math.max(largestDigitMap[largestDigit], num);
        }

        return maxSum;
    }

    private int findLargestDigit(int num) {
        int largestDigit = 0;
        String numStr = String.valueOf(num);
        for (int i = 0; i < numStr.length(); i++) {
            int digit = Character.getNumericValue(numStr.charAt(i));
            largestDigit = Math.max(largestDigit, digit);
        }
        return largestDigit;
    }
}

Time Complexity

O(n), where n is the length of the input array nums. We iterate through the array only once.

Space Complexity

O(1), since the largestDigitMap array has a fixed size of 10, regardless of the input size.