Given an array nums, find two indices i and j (i != j) such that the digit sum of nums[i] equals the digit sum of nums[j], and return the maximum value of nums[i] + nums[j]. Return -1 if no such pair exists.

Examples

Example 1:

Input: nums = [18,43,36,13,7]
Output: 54
Explanation:
  digitSum(18) = 9, digitSum(36) = 9
  18 + 36 = 54 is the maximum pair with equal digit sums.

Example 2:

Input: nums = [10,12,19,14]
Output: -1
Explanation: No two numbers share the same digit sum.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9

Thinking Process

To maximize the sum of a pair with equal digit sums, we want the two largest numbers in each digit-sum group.

Key Insight

We don’t need to store all numbers per group – just the largest so far. As we scan, for each number:

  1. Compute its digit sum
  2. If we’ve seen a number with the same digit sum, try pairing with the best one
  3. Update the best for this digit sum

This is the “best seen so far” pattern – same idea as tracking the min price in Best Time to Buy and Sell Stock.

Walk-through

nums = [18, 43, 36, 13, 7]

x=18: digitSum=9,  best[9]=0  → no pair, best[9]=18
x=43: digitSum=7,  best[7]=0  → no pair, best[7]=43
x=36: digitSum=9,  best[9]=18 → pair: 18+36=54, rtn=54, best[9]=36
x=13: digitSum=4,  best[4]=0  → no pair, best[4]=13
x=7:  digitSum=7,  best[7]=43 → pair: 43+7=50, rtn=max(54,50)=54, best[7]=43

Answer: 54 ✓

Why best Array of Size 100?

Max digit sum occurs for 999,999,999 = 9 × 9 = 81. An array of size 100 covers all possible digit sums with margin.

Greedy choice pick locally best after sorting

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Sort + greedy (this problem) O(n log n) O(1) Interval scheduling, assignment
Local greedy choice O(n) O(1) Jump game, gas station
Greedy + heap O(n log n) O(n) Merge streams, room allocation
Exchange argument O(n) O(1) Prove greedy choice is safe

Solution

class Solution {
public:
    int maximumSum(vector<int>& nums) {
        vector<int> best(100, 0);
        int rtn = -1;
        for (int x : nums) {
            int s = digitSum(x);
            if (best[s] > 0) {
                rtn = max(rtn, best[s] + x);
            }
            best[s] = max(best[s], x);
        }
        return rtn;
    }

private:
    int digitSum(int x) {
        int s = 0;
        while (x) {
            s += x % 10;
            x /= 10;
        }
        return s;
    }
};

Solution Explanation

Approach: Sort + greedy (this problem)

Key idea: To maximize the sum of a pair with equal digit sums, we want the two largest numbers in each digit-sum group.

How the code works:

  1. Compute its digit sum
  2. If we’ve seen a number with the same digit sum, try pairing with the best one
  3. Update the best for this digit sum

Walkthrough — input nums = [18,43,36,13,7], expected output 54:

digitSum(18) = 9, digitSum(36) = 9 18 + 36 = 54 is the maximum pair with equal digit sums.

Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Key Takeaways

  • “Best pair in a group” = track the best seen so far per group, check pair on each new element
  • Using a fixed-size array instead of a hash map leverages the bounded digit-sum range for better constants
  • The “update after pairing” order is critical – pair with the old best, then potentially replace it

References

Template Reference