Max Pair Sum in an Array - Solution & Explanation
Problem Statement
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] <= 104
Approach Overview
Problem 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 1: HashMap-Based Approach
This approach involves using a HashMap to group numbers by their largest digit. The key idea is to find the largest digit in each number and use this digit as a key in the HashMap. For each group (specific largest digit), try to find two numbers that sum to the maximum value. If no such pair exists, return -1.
We use an array indexed from 0 to 9 to store the largest sum of pairs sharing the same largest digit. For each number, determine its largest digit and try to update the array entry corresponding to this digit by forming potential sums. Finally, we return the maximum value found, or -1 if no valid pair is possible.
Complexity
Time Complexity: O(n). We iterate over the numbers array once and perform a constant-time check/insert for each number.
Space Complexity: O(1). We use a fixed-size integer array for the digits.
Approach 2: Sort and Two-Pointers Approach
This approach sorts numbers based on their largest digit and then uses a two-pointer technique to find the maximum sum of numbers with the same largest digit. While straightforward, it assumes a sorting cost, thus this might be less efficient than a pure HashMap solution.
The logic involves sorting the numbers based on their largest digit using qsort and a comparator function. Once sorted, the algorithm attempts to find the maximum sum of consecutive elements with the same largest digit.
Complexity
Time Complexity: O(n log n) because of sorting.
Space Complexity: O(1) as no additional storage is used except for the constant pointers.
Approach 3: Enumeration
First, we initialize the answer variable ans=-1. Next, we directly enumerate all pairs (nums[i], nums[j]) where i \lt j, and calculate their sum v=nums[i] + nums[j]. If v is greater than ans and the largest digit of nums[i] and nums[j] are the same, then we update ans with v.
The time complexity is O(n^2 times log M), where n is the length of the array and M is the maximum value in the array.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| HashMap-Based Approach | Time Complexity: O(n). We iterate over the numbers array once and perform a constant-time check/insert for each number. |
| Sort and Two-Pointers Approach | Time Complexity: O(n log n) because of sorting. |
| Enumeration | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Max Pair Sum in an Array | Leetcode 2815 | Hashing | C++ • Tech Courses • 1,514 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Max Pair Sum in an Array easy or hard?
Max Pair Sum in an Array Python/Java solution
How to solve Max Pair Sum in an Array in O(n)?
What is the best approach for Max Pair Sum in an Array?
Is Max Pair Sum in an Array asked at Google/Amazon/Meta?
What data structure is used in Max Pair Sum in an Array?
What is the time complexity of Max Pair Sum in an Array?
Ready to solve this problem?
Practice Max Pair Sum in an Array with our built-in code editor and test cases.
Practice on FleetCode