Max Pair Sum in an Array

• Initialize a variable maxSum to -1.
• Create a helper function getLargestDigit(int n) that returns the largest digit in a number n.
• Use a nested loop to iterate through every unique pair of numbers (nums[i], nums[j]) in the array.
• For each pair, find the largest digit of nums[i] and nums[j].
• If the largest digits are the same, calculate their sum.
• Update maxSum with the current pair's sum if it is greater than the existing maxSum.
• After checking all pairs, return maxSum.

The core idea is to use nested loops to generate all unique pairs (nums[i], nums[j]) where i < j. A helper function, getLargestDigit(n), is used to find the largest digit of any given number n. This function works by repeatedly taking the number modulo 10 to get the last digit and dividing by 10 to remove it, keeping track of the maximum digit seen. Inside the inner loop, we call this helper function for both nums[i] and nums[j]. If their largest digits are equal, we compute their sum and compare it with a running maximum, updating it if the new sum is larger. We initialize the maximum sum to -1, which is the value to be returned if no valid pair is found.

1class Solution {2    private int getLargestDigit(int n) {3        int maxDigit = 0;4        String s = Integer.toString(n);5        for (char c : s.toCharArray()) {6            maxDigit = Math.max(maxDigit, c - '0');7        }8        return maxDigit;9    }10 11    public int maxSum(int[] nums) {12        int n = nums.length;13        int maxSum = -1;14        for (int i = 0; i < n; i++) {15            for (int j = i + 1; j < n; j++) {16                if (getLargestDigit(nums[i]) == getLargestDigit(nums[j])) {17                    maxSum = Math.max(maxSum, nums[i] + nums[j]);18                }19            }20        }21        return maxSum;22    }23}

• Create a hash map, groups, where keys are digits (0-9) and values are lists of integers.
• Iterate through the input array nums. For each number num:
  • Find its largest digit d.
  • Add num to the list at groups.get(d).
• Initialize maxSum = -1.
• Iterate through each list in the groups map's values.
• If a list has two or more numbers, find the two largest numbers in that list.
• Calculate their sum and update maxSum if this sum is greater.
• Return maxSum.

First, we iterate through the input array nums once. For each number, we compute its largest digit. We then use a hash map (e.g., Map<Integer, List<Integer>>) to store these numbers. The largest digit serves as the key, and we add the number to the list associated with that key. After populating the map, we iterate through its values (the lists of numbers). For any list that contains two or more numbers, we know a valid pair can be formed. To find the maximum sum for a given group, we need the two largest numbers from its list. We can find these two numbers in a single pass through the list, which is more efficient than sorting the entire list. We keep track of the overall maximum sum found across all groups and return it.

1import java.util.*;2 3class Solution {4    private int getLargestDigit(int n) {5        int maxDigit = 0;6        while (n > 0) {7            maxDigit = Math.max(maxDigit, n % 10);8            n /= 10;9        }10        return maxDigit;11    }12 13    public int maxSum(int[] nums) {14        Map<Integer, List<Integer>> groups = new HashMap<>();15        for (int num : nums) {16            int d = getLargestDigit(num);17            groups.computeIfAbsent(d, k -> new ArrayList<>()).add(num);18        }19 20        int maxSum = -1;21        for (List<Integer> list : groups.values()) {22            if (list.size() >= 2) {23                Collections.sort(list, Collections.reverseOrder());24                maxSum = Math.max(maxSum, list.get(0) + list.get(1));25            }26        }27        return maxSum;28    }29}

• Initialize maxSum = -1.
• Initialize an integer array maxForDigit of size 10 with all zeros. This array will store the largest number seen so far for each largest digit.
• For each num in the input array nums:
  • Calculate its largest digit, d.
  • If maxForDigit[d] is not zero, it means we've seen a previous number with the same largest digit. We form a pair with num and maxForDigit[d] and update maxSum.
  • Update maxForDigit[d] to be the maximum of its current value and num.
• Return maxSum.

We use an array of size 10, say maxForDigit, to store the largest number encountered for each digit from 0 to 9. This array is initialized with zeros. We iterate through the input array nums just once. For each num, we first find its largest digit, d. Then, we check maxForDigit[d]. If it's greater than 0, it means we have already seen at least one number with the same largest digit d. The value maxForDigit[d] holds the largest of those previous numbers. We can form a pair (num, maxForDigit[d]) and update our global maxSum. Finally, regardless of whether a pair was formed, we update maxForDigit[d] with num if num is larger than the current value stored. This ensures that for any future number with largest digit d, it will be paired with the largest number seen so far. This method cleverly finds the maximum pair sum without needing to store all numbers, leading to optimal space complexity.

1class Solution {2    private int getLargestDigit(int n) {3        int maxDigit = 0;4        while (n > 0) {5            maxDigit = Math.max(maxDigit, n % 10);6            n /= 10;7        }8        return maxDigit;9    }10 11    public int maxSum(int[] nums) {12        int maxSum = -1;13        int[] maxForDigit = new int[10];14 15        for (int num : nums) {16            int d = getLargestDigit(num);17            if (maxForDigit[d] != 0) {18                maxSum = Math.max(maxSum, num + maxForDigit[d]);19            }20            maxForDigit[d] = Math.max(maxForDigit[d], num);21        }22 23        return maxSum;24    }25}