Max Sum of a Pair With Equal Sum of Digits - Video Solutions

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.