Max Sum of a Pair With Equal Sum of Digits - Solution & Explanation
Problem Statement
You are given a 0-indexed array nums consisting of positive integers. You can choose two indices i and j, such that i != j, and the sum of digits of the number nums[i] is equal to that of nums[j].
Return the maximum value of nums[i] + nums[j] that you can obtain over all possible indices i and j that satisfy the conditions.
Example 1:
Input: nums = [18,43,36,13,7] Output: 54 Explanation: The pairs (i, j) that satisfy the conditions are: - (0, 2), both numbers have a sum of digits equal to 9, and their sum is 18 + 36 = 54. - (1, 4), both numbers have a sum of digits equal to 7, and their sum is 43 + 7 = 50. So the maximum sum that we can obtain is 54.
Example 2:
Input: nums = [10,12,19,14] Output: -1 Explanation: There are no two numbers that satisfy the conditions, so we return -1.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 109
Approach Overview
Problem Overview: You are given an array of integers. Two numbers can form a valid pair only if the sum of their digits is the same. Among all such pairs, return the maximum possible value of nums[i] + nums[j]. If no pair shares the same digit sum, return -1.
Approach 1: Hash Map Grouping (O(n) time, O(n) space)
Compute the digit sum for every number and group numbers that share the same value. A hash table maps digitSum → list or best values. While iterating through the array, calculate the digit sum in O(d) where d is the number of digits. For each group, track the two largest numbers. If a group contains at least two elements, compute their sum and update the global maximum.
This approach works because only numbers with identical digit sums can form valid pairs. Instead of checking every pair, the hash map restricts comparisons to numbers within the same group. The total work is linear with respect to the array size. Time complexity is O(n), and space complexity is O(n) for storing grouped values.
Approach 2: Optimized Direct Pair Processing (O(n) time, O(1)–O(n) space)
The optimized approach avoids storing full groups. Maintain a hash map where each key is a digit sum and the value is the largest number seen so far with that digit sum. Iterate once through the array. For each number, compute its digit sum and check the map.
If the digit sum already exists, you immediately have a candidate pair: the current number plus the stored maximum. Update the answer if this pair is larger. Then update the stored value with max(existing, current). This ensures the map always keeps the best candidate for future pairs.
This technique turns grouping into a streaming process. Each element performs constant-time hash lookup and update. The overall time complexity remains O(n) and the space complexity is O(k), where k is the number of unique digit sums (at most ~82 for 32‑bit integers).
Alternative Idea: Sorting Within Groups (O(n log n) time, O(n) space)
You can also group numbers by digit sum, then sort each group and take the top two values. Sorting increases the time complexity to O(n log n), making it slower than the hash-based approach. It is still useful conceptually when exploring grouping strategies with sorting or when extending the problem to more complex ranking logic.
Recommended for interviews: The optimized direct processing method is the expected solution. It demonstrates efficient use of a hash table and avoids unnecessary storage. Showing the grouping idea first proves you understand the constraint (equal digit sums), but the single-pass optimization shows strong problem-solving instincts and attention to time complexity.
Approach 1: Approach 1: Hash Map Grouping
This approach involves using a hash map to collect numbers with the same digit sum as keys and their corresponding numbers as values. Then, for each group (that has more than one number), calculate the maximal possible sum of any two numbers in that group.
This Python function calculates the digit sum of each number and stores numbers in a dictionary keyed by their digit sum. It then checks if each key has multiple numbers, sorts them, and picks the largest two to calculate their sum.
Code
Python
C++
Java
JavaScript
C#
Complexity
Time Complexity: O(n log k), where n is the number of elements and k is the average length of the list stored in the hash map.
Space Complexity: O(n) for the hash map.
Approach 2: Approach 2: Optimized Direct Pair Processing
In this approach, instead of sorting within each digit group, use a max heap (priority queue) to track the two largest numbers efficiently. Maintain the largest two numbers seen on-the-fly for each digit sum group.
This Python solution uses a heap to keep track of the top two numbers in each digit group efficiently. Heap operations ensure that the complexity remains lower than sorting.
Code
Python
C++
Java
JavaScript
C#
Complexity
Time Complexity: O(n log k), where k is typically small, so it's closer to O(n). Space Complexity: O(n) for the hash map.
Approach 3: Hash Table
We can use a hash table d to record the maximum value corresponding to each digit sum, and initialize an answer variable ans = -1.
Next, we traverse the array nums. For each number v, we calculate its digit sum x. If x exists in the hash table d, then we update the answer ans = max(ans, d[x] + v). Then update the hash table d[x] = max(d[x], v).
Finally, return the answer ans.
Since the maximum element in nums is 10^9, the maximum digit sum is 9 times 9 = 81. We can directly define an array d of length 100 to replace the hash table.
The time complexity is O(n times log M), and the space complexity is O(D). Here, n is the length of the array nums, and M and D are the maximum value of the elements in the array nums and the maximum value of the digit sum, respectively. In this problem, M leq 10^9, D leq 81.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Hash Map Grouping | Time Complexity: O(n log k), where n is the number of elements and k is the average length of the list stored in the hash map. |
| Approach 2: Optimized Direct Pair Processing | Time Complexity: O(n log k), where k is typically small, so it's closer to O(n). Space Complexity: O(n) for the hash map. |
| Hash Table | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map Grouping | O(n) | O(n) | Clear grouping logic when exploring pairs with the same digit sum |
| Optimized Direct Pair Processing | O(n) | O(k) | Best general solution; single pass with constant-time hash lookups |
| Sort Numbers Within Groups | O(n log n) | O(n) | Useful when additional ranking or ordering inside groups is required |
Video Solution
Max Sum of a Pair With Equal Sum of Digits | 4 Approaches | Leetcode 2342 | codestorywithMIK • codestorywithMIK • 7,046 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Max Sum of a Pair With Equal Sum of Digits easy or hard?
Max Sum of a Pair With Equal Sum of Digits Python/Java solution
How to solve Max Sum of a Pair With Equal Sum of Digits in O(n)?
What is the best approach for Max Sum of a Pair With Equal Sum of Digits?
Is Max Sum of a Pair With Equal Sum of Digits asked at Google/Amazon/Meta?
What data structure is used in Max Sum of a Pair With Equal Sum of Digits?
What is the time complexity of Max Sum of a Pair With Equal Sum of Digits?
Ready to solve this problem?
Practice Max Sum of a Pair With Equal Sum of Digits with our built-in code editor and test cases.
Practice on FleetCode