Max Pair Sum in an Array

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.

Examples

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] <= 10^4

Solution

Method 1 – Hash Map by Largest Digit

Intuition

For each number, group numbers by their largest digit. The answer is the maximum sum of any two numbers in the same group. We use a hash map to track the largest and second largest numbers for each digit.

Approach

1. For each number, compute its largest digit.
2. For each digit (0-9), keep the two largest numbers seen so far.
3. For each digit, if there are at least two numbers, compute their sum and update the answer.
4. Return the maximum sum found, or -1 if no such pair exists.

Code

C++

class Solution {
public:
    int maxSum(vector<int>& nums) {
        vector<int> mx(10, -1), smx(10, -1);
        for (int x : nums) {
            int d = 0, t = x;
            while (t) { d = max(d, t % 10); t /= 10; }
            if (x > mx[d]) { smx[d] = mx[d]; mx[d] = x; }
            else if (x > smx[d]) { smx[d] = x; }
        }
        int ans = -1;
        for (int d = 0; d < 10; ++d)
            if (mx[d] != -1 && smx[d] != -1)
                ans = max(ans, mx[d] + smx[d]);
        return ans;
    }
};

Go

func maxSum(nums []int) int {
    mx := make([]int, 10)
    smx := make([]int, 10)
    for i := range mx {
        mx[i], smx[i] = -1, -1
    }
    for _, x := range nums {
        d, t := 0, x
        for t > 0 {
            if t%10 > d {
                d = t % 10
            }
            t /= 10
        }
        if x > mx[d] {
            smx[d] = mx[d]
            mx[d] = x
        } else if x > smx[d] {
            smx[d] = x
        }
    }
    ans := -1
    for d := 0; d < 10; d++ {
        if mx[d] != -1 && smx[d] != -1 && mx[d]+smx[d] > ans {
            ans = mx[d] + smx[d]
        }
    }
    return ans
}

Java

class Solution {
    public int maxSum(int[] nums) {
        int[] mx = new int[10], smx = new int[10];
        Arrays.fill(mx, -1); Arrays.fill(smx, -1);
        for (int x : nums) {
            int d = 0, t = x;
            while (t > 0) { d = Math.max(d, t % 10); t /= 10; }
            if (x > mx[d]) { smx[d] = mx[d]; mx[d] = x; }
            else if (x > smx[d]) { smx[d] = x; }
        }
        int ans = -1;
        for (int d = 0; d < 10; d++)
            if (mx[d] != -1 && smx[d] != -1)
                ans = Math.max(ans, mx[d] + smx[d]);
        return ans;
    }
}

Kotlin

class Solution {
    fun maxSum(nums: IntArray): Int {
        val mx = IntArray(10) { -1 }
        val smx = IntArray(10) { -1 }
        for (x in nums) {
            var d = 0; var t = x
            while (t > 0) { d = maxOf(d, t % 10); t /= 10 }
            if (x > mx[d]) { smx[d] = mx[d]; mx[d] = x }
            else if (x > smx[d]) { smx[d] = x }
        }
        var ans = -1
        for (d in 0..9)
            if (mx[d] != -1 && smx[d] != -1)
                ans = maxOf(ans, mx[d] + smx[d])
        return ans
    }
}

Python

class Solution:
    def maxSum(self, nums: list[int]) -> int:
        mx = [-1] * 10
        smx = [-1] * 10
        for x in nums:
            d, t = 0, x
            while t:
                d = max(d, t % 10)
                t //= 10
            if x > mx[d]:
                smx[d] = mx[d]
                mx[d] = x
            elif x > smx[d]:
                smx[d] = x
        ans = -1
        for d in range(10):
            if mx[d] != -1 and smx[d] != -1:
                ans = max(ans, mx[d] + smx[d])
        return ans

Rust

impl Solution {
    pub fn max_sum(nums: Vec<i32>) -> i32 {
        let mut mx = vec![-1; 10];
        let mut smx = vec![-1; 10];
        for &x in &nums {
            let mut d = 0;
            let mut t = x;
            while t > 0 {
                d = d.max(t % 10);
                t /= 10;
            }
            if x > mx[d as usize] {
                smx[d as usize] = mx[d as usize];
                mx[d as usize] = x;
            } else if x > smx[d as usize] {
                smx[d as usize] = x;
            }
        }
        let mut ans = -1;
        for d in 0..10 {
            if mx[d] != -1 && smx[d] != -1 {
                ans = ans.max(mx[d] + smx[d]);
            }
        }
        ans
    }
}

TypeScript

class Solution {
    maxSum(nums: number[]): number {
        const mx = Array(10).fill(-1), smx = Array(10).fill(-1);
        for (const x of nums) {
            let d = 0, t = x;
            while (t > 0) { d = Math.max(d, t % 10); t = Math.floor(t / 10); }
            if (x > mx[d]) { smx[d] = mx[d]; mx[d] = x; }
            else if (x > smx[d]) { smx[d] = x; }
        }
        let ans = -1;
        for (let d = 0; d < 10; d++)
            if (mx[d] !== -1 && smx[d] !== -1)
                ans = Math.max(ans, mx[d] + smx[d]);
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n log A), where n is the length of nums and A is the maximum value in nums, for digit extraction.
• 🧺 Space complexity: O(1), for storing the two largest numbers for each digit.