# Max Pair Sum in an Array
**Difficulty:** EASY
[External](https://leetcode.com/problems/max-pair-sum-in-an-array)
Canonical: https://scaleengineer.com/dsa/problems/max-pair-sum-in-an-array
**Data structures:** Array, Hash Table
---
## Problem
You are given an integer array `nums`. You have to find the **maximum** sum of a pair of numbers from `nums` such that the **largest digit** in both numbers is equal.

For example, 2373 is made up of three distinct digits: 2, 3, and 7, where 7 is the largest among them.

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

**Example 1:**

**Input:** nums = \[112,131,411\]

**Output:** \-1

**Explanation:**

Each numbers largest digit in order is \[2,3,4\].

**Example 2:**

**Input:** nums = \[2536,1613,3366,162\]

**Output:** 5902

**Explanation:**

All the numbers have 6 as their largest digit, so the answer is 2536 + 3366 = 5902.

**Example 3:**

**Input:** nums = \[51,71,17,24,42\]

**Output:** 88

**Explanation:**

Each number's largest digit in order is \[5,7,7,4,4\].

So we have only two possible pairs, 71 + 17 = 88 and 24 + 42 = 66.

**Constraints:**

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

# Approaches
## Brute-Force Iteration
This approach involves checking every possible pair of numbers in the array. For each pair, we determine if they share the same largest digit. If they do, we calculate their sum and update the maximum sum found so far. This method is straightforward but not the most efficient.
**Time:** O(N^2 * D), where N is the number of elements in `nums` and D is the maximum number of digits in a number. Since D is small and constant (at most 5 for numbers up to 10^4), the complexity is effectively O(N^2). We iterate through approximately N^2 / 2 pairs. · **Space:** O(1), as we only use a few variables to store the maximum sum and loop indices, regardless of the input size.
**Pros:** Simple to understand and implement.; Uses constant extra space, O(1).
**Cons:** The time complexity is O(N^2), which is inefficient for large input arrays.; It performs redundant calculations for the largest digit of each number.
### Explanation
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.

```java
class Solution {
    private int getLargestDigit(int n) {
        int maxDigit = 0;
        String s = Integer.toString(n);
        for (char c : s.toCharArray()) {
            maxDigit = Math.max(maxDigit, c - '0');
        }
        return maxDigit;
    }

    public int maxSum(int[] nums) {
        int n = nums.length;
        int maxSum = -1;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (getLargestDigit(nums[i]) == getLargestDigit(nums[j])) {
                    maxSum = Math.max(maxSum, nums[i] + nums[j]);
                }
            }
        }
        return maxSum;
    }
}
```
### Algorithm
- 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`.

## Grouping with a Hash Map
A more optimized approach is to group numbers by their largest digit. By doing this, we avoid redundant comparisons. We can use a hash map where keys are the largest digits (0-9) and values are lists of numbers that have that largest digit. After grouping, we find the pair with the maximum sum within each group.
**Time:** O(N log N) if sorting each group, or O(N*D) if finding the top two elements linearly. The provided code uses sorting, making it O(N log N) in the worst case where all numbers fall into one group. An O(N*D) or O(N) solution is possible by finding the top two elements in linear time for each group. · **Space:** O(N), as in the worst-case scenario, the hash map might need to store all N numbers from the input array.
**Pros:** Significantly faster than the brute-force approach with linear time complexity.; Groups numbers logically, which can be a useful intermediate step for similar problems.
**Cons:** Requires extra space proportional to the input size to store the groups of numbers.
### Explanation
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.

```java
import java.util.*;

class Solution {
    private int getLargestDigit(int n) {
        int maxDigit = 0;
        while (n > 0) {
            maxDigit = Math.max(maxDigit, n % 10);
            n /= 10;
        }
        return maxDigit;
    }

    public int maxSum(int[] nums) {
        Map<Integer, List<Integer>> groups = new HashMap<>();
        for (int num : nums) {
            int d = getLargestDigit(num);
            groups.computeIfAbsent(d, k -> new ArrayList<>()).add(num);
        }

        int maxSum = -1;
        for (List<Integer> list : groups.values()) {
            if (list.size() >= 2) {
                Collections.sort(list, Collections.reverseOrder());
                maxSum = Math.max(maxSum, list.get(0) + list.get(1));
            }
        }
        return maxSum;
    }
}
```
### Algorithm
- 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`.

## Single-Pass with an Array
This is the most efficient approach, combining the logic into a single pass over the input array while using constant extra space. The idea is to keep track of the largest number seen so far for each possible largest digit (0-9).
**Time:** O(N * D), where N is the number of elements and D is the number of digits. We iterate through the array once, and for each element, we perform a constant number of operations plus the digit calculation. This simplifies to O(N) linear time. · **Space:** O(1). We only use an array of fixed size 10 to store the maximum numbers for each digit. The space requirement is constant and does not depend on the size of the input array.
**Pros:** Optimal time complexity (linear).; Optimal space complexity (constant).; Requires only a single pass through the data.
**Cons:** The logic might be slightly less intuitive at first glance compared to the grouping approach.
### Explanation
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.

```java
class Solution {
    private int getLargestDigit(int n) {
        int maxDigit = 0;
        while (n > 0) {
            maxDigit = Math.max(maxDigit, n % 10);
            n /= 10;
        }
        return maxDigit;
    }

    public int maxSum(int[] nums) {
        int maxSum = -1;
        int[] maxForDigit = new int[10];

        for (int num : nums) {
            int d = getLargestDigit(num);
            if (maxForDigit[d] != 0) {
                maxSum = Math.max(maxSum, num + maxForDigit[d]);
            }
            maxForDigit[d] = Math.max(maxForDigit[d], num);
        }

        return maxSum;
    }
}
```
### Algorithm
- 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`.

# Solutions
### Java

```java
class Solution {
public
  int maxSum(int[] nums) {
    int ans = -1;
    int n = nums.length;
    for (int i = 0; i < n; ++i) {
      for (int j = i + 1; j < n; ++j) {
        int v = nums[i] + nums[j];
        if (ans < v && f(nums[i]) == f(nums[j])) {
          ans = v;
        }
      }
    }
    return ans;
  }
private
  int f(int x) {
    int y = 0;
    for (; x > 0; x /= 10) {
      y = Math.max(y, x % 10);
    }
    return y;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxSum(vector<int> &nums) {
    int ans = -1;
    int n = nums.size();
    auto f = [](int x) {
      int y = 0;
      for (; x; x /= 10) {
        y = max(y, x % 10);
      }
      return y;
    };
    for (int i = 0; i < n; ++i) {
      for (int j = i + 1; j < n; ++j) {
        int v = nums[i] + nums[j];
        if (ans < v && f(nums[i]) == f(nums[j])) {
          ans = v;
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxSum(self, nums: List[int]) -> int: ans = - 1 for i, x in enumerate(nums): for y in nums[i + 1:]: v = x + y if ans < v and max(str(x)) == max(str(y)): ans = v return ans

```