<p>You are given a <strong>0-indexed</strong> array <code>nums</code> consisting of <strong>positive</strong> integers. You can choose two indices <code>i</code> and <code>j</code>, such that <code>i != j</code>, and the sum of digits of the number <code>nums[i]</code> is equal to that of <code>nums[j]</code>.</p>

<p>Return <em>the <strong>maximum</strong> value of </em><code>nums[i] + nums[j]</code><em> that you can obtain over all possible indices </em><code>i</code><em> and </em><code>j</code><em> that satisfy the conditions.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [18,43,36,13,7]
<strong>Output:</strong> 54
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [10,12,19,14]
<strong>Output:</strong> -1
<strong>Explanation:</strong> There are no two numbers that satisfy the conditions, so we return -1.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution:
    """
    Goal: Find the maximum sum of two numbers with equal digit sums.
    
    Approach: Hash Map
        Use a hash map to store the largest number for each digit sum.
        As we iterate through the numbers,
            calculate its digit sum and check if we've seen this digit sum before
            if so, calculate the sum of these two numbers and update answer
            update hash map
        
        Complexity
            Time = O(N * logM), where N is the number of integers and M is the largest integer
            Space = O(K), where K is the number of unique digit sums
    """
    from collections import defaultdict
    def maximumSum(self, nums: List[int]) -> int:
        def getDigitSum(num: int) -> int:
            digitSum = 0

            while num > 0:
                digitSum += num % 10
                num //= 10
            
            return digitSum

        
        maxVals = defaultdict(int)  # digit sum: largest number with this sum
        maxSum = -1                 # answer

        for num in nums:
            dSum = getDigitSum(num)
            if dSum in maxVals:
                maxSum = max(maxSum, maxVals[dSum] + num)
            maxVals[dSum] = max(maxVals[dSum], num)
        
        return maxSum

                


        
743