Maximize Sum of Two Numbers with Same Digit Sum 💡
IntuitionThe goal of this problem is to find the maximum sum of two numbers from an array where the sum of their digits is the same. If multiple pairs of number
### Intuition
The goal of this problem is to find the maximum sum of two numbers from an array where the sum of their digits is the same. If multiple pairs of numbers have the same sum of digits, we need to choose the pair with the largest sum. The approach can be broken down into grouping the numbers based on their digit sums and then selecting the two largest numbers from each group to find the maximum sum.

### Approach
1. **Digit Sum Calculation**: For each number in the array, calculate the sum of its digits. This will help in grouping numbers that have the same digit sum.
   
2. **Group by Digit Sum**: Use a `HashMap` where the key is the sum of digits, and the value is a `PriorityQueue` (max-heap) to store numbers with that particular digit sum. The `PriorityQueue` will help us efficiently retrieve the largest and second-largest numbers.

3. **Update Maximum Sum**: For each digit sum group (i.e., for each key in the map), we check if the group contains at least two numbers. If it does, we extract the two largest numbers from the `PriorityQueue`, calculate their sum, and update the `maxSum` if the current sum is larger than the previously recorded maximum.

4. **Return the Result**: Finally, return the `maxSum`, which is the largest sum obtained from any group.

### Complexity

**Time Complexity**:  
Calculating the digit sum for each number takes *O(d)* time, where *d* is the number of digits in a number (this is at most 10 for typical integers).  
For each number, inserting it into the `PriorityQueue` takes *O(log k)*, where *k* is the number of elements in the group (sum of digits).  
So, the overall time complexity is *O(n * log k)*, where *n* is the number of elements in the array, and *k* is the number of elements with the same digit sum (which is usually small compared to *n*).

**Space Complexity**:  
The space complexity is *O(n)*, where *n* is the number of elements in the array, as we need to store all the elements in the map and priority queues.
### Code
```java
class Solution {
    public int maximumSum(int[] nums) {
        Map<Integer, PriorityQueue<Integer>> map = new HashMap<>();
        
        // Step 1: Group numbers by the sum of their digits
        for (int num : nums) {
            int sum = getSum(num);
            map.putIfAbsent(sum, new PriorityQueue<>((a, b) -> Integer.compare(b, a))); // Max-heap for each sum group
            map.get(sum).offer(num); // Add the number to the priority queue for that sum of digits
        }

        int maxSum = -1;

        // Step 2: Find the maximum sum of two largest numbers in each group
        for (PriorityQueue<Integer> pq : map.values()) {
            if (pq.size() > 1) {
                int first = pq.poll();  // Get the largest element
                int second = pq.poll(); // Get the second largest element
                maxSum = Math.max(maxSum, first + second); // Update maxSum
            }
        }

        return maxSum;
    }

    // Helper function to calculate the sum of digits of a number
    public int getSum(int num) {
        int sum = 0;
        while (num != 0) {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }
}
```


---

If this solution helps, **upvote the post** 👍!
['Array', 'Hash Table', 'Sorting', 'Heap (Priority Queue)', 'Java']