<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>


# Improvment: 
# we don't need to store all the numbers in the group. We can improve the time complexity and average space complexity by only saving the largest number seen so far for each digit sum.
# 1. define a hashmap
#       key: sum of digits
#       value: the largest number seen so far for the digit sum.
class Solution:
    def maximumSum(self, nums: List[int]) -> int:
        result = -1
        hashmap = {}
        for i in range(len(nums)):
            num = nums[i]

            # calculate the sum of digit 
            sum_digit = 0
            while num > 0:
                sum_digit += num % 10
                num = num // 10

            # check sum_digit in hashmap
            if sum_digit in hashmap:
                # calculate the sum, compare it with the result, and update 
                result = max(result, nums[i] + hashmap[sum_digit]) 
                # update the hashmap if nums[i] > hashmap[sum_digit]
                hashmap[sum_digit] = max(hashmap[sum_digit], nums[i])     
            else:
                hashmap[sum_digit] = nums[i]
        return result

# Time: O(n) 
# Space: O(n)
737