Watch 10 video solutions for Max Pair Sum in an Array, a easy level problem involving Array, Hash Table. This walkthrough by Tech Courses has 1,415 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1001 <= nums[i] <= 104Problem Overview: You are given an integer array and must find the maximum sum of a pair of numbers where both numbers share the same highest digit. If no such pair exists, return -1. The key observation is that numbers can only form a valid pair if their largest digit (0–9) matches.
Approach 1: HashMap-Based Approach (O(n) time, O(1) space)
Scan the array once and compute the maximum digit of each number. Use a hash map (or fixed array of size 10) where the key is the maximum digit and the value stores the largest number seen so far with that digit. For each new number, check if another number with the same maximum digit already exists. If it does, compute the pair sum and update the global maximum. Then update the stored value if the current number is larger. Each element is processed once and digit extraction is constant time, giving O(n) time and O(1) extra space since the digit range is fixed.
This approach relies on quick lookups using a hash table and simple iteration over the array. It works well because the grouping condition (maximum digit) has only 10 possible values.
Approach 2: Sort and Two-Pointers Approach (O(n log n) time, O(1) extra space)
Another option is to sort the array in descending order and compare numbers with the same maximum digit. After sorting, compute the largest digit for each number and group or scan adjacent candidates that share the same digit. Because larger numbers appear first, the first valid pair encountered for a digit often produces the maximum sum. Sorting costs O(n log n), and scanning afterward is linear.
This method uses sorting and sometimes a two pointers style scan to evaluate candidate pairs efficiently. It is easier to reason about when you want the largest values considered first, but it is slower than the hash map solution due to the sorting step.
Recommended for interviews: The hash map approach is the expected optimal solution. It shows that you recognized the constraint that the maximum digit ranges only from 0–9 and used that to group numbers efficiently. Brute-force pair checking would take O(n^2), which demonstrates basic understanding, but the O(n) hash-based grouping shows stronger problem-solving skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap-Based Grouping by Max Digit | O(n) | O(1) | Best general solution. Efficient when grouping elements by a small fixed key range (digits 0–9). |
| Sort and Two-Pointers Scan | O(n log n) | O(1) | Useful when working with sorted arrays or when you want the largest candidates evaluated first. |