✅ Easy to Understand | Intuitive Approach using Hash Table | Detailed Video Explanation🔥
IntuitionThe problem requires finding the maximum sum of two numbers that share the same sum of digits. To solve this efficiently, we can use a hash map to grou
# Intuition
The problem requires finding the maximum sum of two numbers that share the same sum of digits. To solve this efficiently, we can use a **hash map** to group numbers by their digit sum and track the largest values.  

# Approach
1. **Compute the digit sum** of each number in the array.
2. Use a **hash map** (`map`) where the key is the digit sum and the value is the largest number seen so far with that digit sum.
3. As we iterate through the array:
   - If the digit sum already exists in `map`, update the answer (`ans`) with the sum of the current number and the stored maximum.
   - Update the map to store the **maximum** number for each digit sum key.
   - If the digit sum is not found in `map`, store the current number.
4. Return `ans`, which keeps track of the maximum sum found.

# Complexity
- **Time complexity:**  
  - We iterate through the array once: **O(n)**  
  - Computing the digit sum of each number takes **O(k)** (where `k` is the number of digits, which is at most log(num)), but this is considered constant for practical constraints.  
  - Overall, the solution runs in **O(n)**.

- **Space complexity:**  
  - We use a hash map to store the maximum number for each digit sum, which in the worst case could have **O(n)** entries.
  - Thus, the space complexity is **O(n)**.


# Code
```java []
class Solution {
    public int maximumSum(int[] nums) {
        int n = nums.length;
        Map<Integer, Integer> map = new HashMap<>(); // Stores the max value for each digit sum key

        int ans = -1; // Initialize answer to -1 (default case if no valid pair is found)
        for(int i = 0; i < n; i++){
            int key = digitsSum(nums[i]); // Compute the sum of digits for the current number

            if(map.containsKey(key)){
                // If a number with the same digit sum exists, update the answer with the maximum sum of the two
                ans = Math.max(ans, map.get(key) + nums[i]);
                
                // Store the maximum value corresponding to this digit sum key
                map.put(key, Math.max(map.get(key), nums[i]));
            } else {
                // If the key is not present, add the number to the map
                map.put(key, nums[i]);
            }
        }
        return ans; // Return the maximum sum found
    }

    // Helper function to calculate the sum of digits of a number
    int digitsSum(int num) {
        int sum = 0;
        while(num > 0){
            sum += num % 10; // Extract the last digit and add it to sum
            num /= 10; // Remove the last digit
        }
        return sum;
    }
}

```

https://youtu.be/3MG2xqmQrws


['Array', 'Hash Table', 'Sorting', 'Java']