2342. Max Sum of a Pair With Equal Sum of Digits

Round 1

Questions: Understanding the Problem:

1. We need to find two indices (i, j) such that:
   • i ≠ j
   • The sum of digits of nums[i] is equal to the sum of digits of nums[j]
   • Their sum nums[i] + nums[j] is maximized
2. If no such pair exists, return -1.

Optimized Approach: HashMap (Dictionary)

1. Compute the sum of digits for each number:
   • Store the largest number seen so far for each digit sum in a dictionary digit_sum_map.
2. Iterate through nums, updating the dictionary:
   • If a number with the same digit sum is already in the map, compute nums[i] + max_so_far and update max_sum.
   • Update digit_sum_map[digit_sum] with the maximum value.

Python Implementation

class Solution(object):
    def maximumSum(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        def sum_of_digits(n):
            return sum(int(d) for d in str(n))  # Compute digit sum
        
        digit_sum_map = {}  # {digit_sum: max_number_with_that_sum}
        max_sum = -1

        for num in nums:
            digit_sum = sum_of_digits(num)

            if digit_sum in digit_sum_map:
                max_sum = max(max_sum, num + digit_sum_map[digit_sum])  # Update max sum
            
            digit_sum_map[digit_sum] = max(digit_sum_map.get(digit_sum, 0), num)  # Keep max num
        
        return max_sum

Complexity Analysis

1. Time Complexity: O(n)

   • Computing sum of digits: O(log M) (where M is max value 10^9, at most 9 iterations)
   • Looping through nums: O(n)
   • Overall Complexity: O(n)

2. Space Complexity: O(n) (for dictionary storing at most n entries)