Max Pair Sum in an Array

Max Pair Sum in an Array

What is this problem about?

The Max Pair Sum in an Array problem provides an integer array. You are asked to find the maximum possible sum of exactly two numbers from the array that share the exact same maximum digit. For example, the maximum digit of 51 is 5, and the maximum digit of 71 is 7. If no two numbers share the same maximum digit, you return -1.

Why is this asked in interviews?

This is a Hash Map and math logic question. Interviewers use it as a screening problem because it requires a candidate to perform a secondary calculation (extracting the max digit) before grouping elements. It tests your ability to categorize items dynamically and keep track of running maximums within those discrete categories.

Algorithmic pattern used

This problem uses a Hash Map / Grouping pattern. Since the maximum digit of any number is strictly between 0 and 9, you can use an array of size 10 (or a Hash Map) to store the largest number seen so far for each possible maximum digit. As you iterate through the array:

1. Find the max digit of the current number.
2. Check your array/map for that digit. If a number already exists there, the sum of current_number + stored_number is a valid pair sum. Update your global max sum.
3. Update the array/map to ensure it always holds the absolute largest number seen for that digit.

Example explanation

Array: [51, 71, 17, 24, 42] Map for max digits: [0,0,0,0,0,0,0,0,0,0]

• 51: Max digit is 5. Map at index 5 is empty. Update Map[5] = 51. Max Sum = -1.
• 71: Max digit is 7. Map at index 7 is empty. Update Map[7] = 71. Max Sum = -1.
• 17: Max digit is 7. Map at index 7 has 71! Valid pair sum: 17 + 71 = 88. Max Sum = 88. Update Map[7] to max(71, 17) -> stays 71.
• 24: Max digit is 4. Map[4] = 24.
• 42: Max digit is 4. Map at index 4 has 24. Pair sum: 42 + 24 = 66. Max Sum remains 88. Update Map[4] to 42. The final maximum sum is 88.

Common mistakes candidates make

A common brute-force mistake is using nested loops to compare every pair of numbers ($O(N^2)$ time), computing the max digit for both numbers on every comparison. This is highly inefficient. Another mistake is using a map to store all numbers associated with a digit and then sorting them later. Since you only care about the maximum pair sum, you only ever need to store the single largest number seen so far to pair with the current number.

Interview preparation tip

When tackling the Max Pair Sum in an Array coding problem, practice writing a rapid getMaxDigit(num) helper function using a while(num > 0) { max = Math.max(max, num % 10); num /= 10; } loop. String conversions (num.toString()) are slow and consume unnecessary memory. Arithmetic operations are much faster and demonstrate a stronger grasp of fundamental math.