LeetCode 2342 - Max Sum of a Pair With Equal Sum of Digits

The problem requires finding the maximum sum of a pair of numbers in an array such that the sum of the digits of both numbers is equal. Specifically, you are given a 0-indexed array nums containing positive integers. You can choose two distinct indices i and j such that i !

leetcodemediumarrayhash-tablesortingheap-(priority-queue)

LeetCode Problem 2342

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Sorting, Heap (Priority Queue)

Solution

Problem Understanding

The problem requires finding the maximum sum of a pair of numbers in an array such that the sum of the digits of both numbers is equal. Specifically, you are given a 0-indexed array nums containing positive integers. You can choose two distinct indices i and j such that i != j, and the sum of digits of nums[i] equals the sum of digits of nums[j]. The goal is to return the maximum value of nums[i] + nums[j] over all valid pairs. If no such pair exists, the function should return -1.

The input nums can be very large (up to 100,000 elements), and individual elements can be as large as 10^9. This means a brute-force approach that compares all pairs would be inefficient. Important edge cases include arrays where all numbers have unique digit sums, arrays of size 1, or arrays with multiple numbers having the same digit sum but only one valid pair. The problem guarantees positive integers, so we do not need to handle zero or negative numbers.

Approaches

A brute-force approach would check every possible pair (i, j) in the array, compute their digit sums, and update the maximum sum if the digit sums match. While correct, this approach has a time complexity of O(n^2), which is prohibitive for n up to 10^5.

The key insight for an optimal solution is that we do not need to track all numbers with the same digit sum-only the two largest numbers for each digit sum. This is because the sum of any pair from the same digit sum group is maximized by choosing the two largest numbers. By using a hash map to group numbers by their digit sums and keeping only the largest two numbers in each group, we can reduce the time complexity to O(n).

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(1) Compare all pairs, compute digit sums each time
Optimal O(n) O(n) Hash map to track max two numbers per digit sum

Algorithm Walkthrough

  1. Initialize a hash map digit_sum_map that maps a digit sum to a list of the two largest numbers with that digit sum.
  2. Iterate over each number num in nums.
  3. Compute the sum of digits of num using a helper function.
  4. If the digit sum is not in digit_sum_map, initialize it with a list containing num.
  5. If the digit sum is in digit_sum_map, update the list to include num while keeping only the two largest numbers.
  6. After processing all numbers, initialize max_sum to -1.
  7. Iterate over each list of numbers in digit_sum_map.
  8. If a list has at least two numbers, compute their sum and update max_sum if it is larger.
  9. Return max_sum.

Why it works: The invariant is that for each digit sum, we are only keeping track of the two largest numbers. This guarantees that when we calculate the sum for each group, we are considering the maximum possible sum for that digit sum. Therefore, iterating over all groups ensures we find the global maximum sum.

Python Solution

from typing import List

class Solution:
    def maximumSum(self, nums: List[int]) -> int:
        def digit_sum(n: int) -> int:
            s = 0
            while n > 0:
                s += n % 10
                n //= 10
            return s
        
        digit_sum_map = {}
        for num in nums:
            s = digit_sum(num)
            if s not in digit_sum_map:
                digit_sum_map[s] = [num]
            else:
                digit_sum_map[s].append(num)
                digit_sum_map[s] = sorted(digit_sum_map[s], reverse=True)[:2]
        
        max_sum = -1
        for numbers in digit_sum_map.values():
            if len(numbers) >= 2:
                max_sum = max(max_sum, numbers[0] + numbers[1])
        
        return max_sum

The implementation first defines a helper function digit_sum to compute the sum of digits for a given number. A hash map stores the largest two numbers for each digit sum. The algorithm then iterates over the numbers, updates the hash map, and finally computes the maximum sum from all digit sum groups.

Go Solution

func maximumSum(nums []int) int {
    digitSum := func(n int) int {
        s := 0
        for n > 0 {
            s += n % 10
            n /= 10
        }
        return s
    }
    
    digitSumMap := make(map[int][]int)
    
    for _, num := range nums {
        s := digitSum(num)
        digitSumMap[s] = append(digitSumMap[s], num)
        if len(digitSumMap[s]) > 2 {
            if digitSumMap[s][0] < digitSumMap[s][1] {
                digitSumMap[s][0], digitSumMap[s][1] = digitSumMap[s][1], digitSumMap[s][0]
            }
            if len(digitSumMap[s]) > 2 {
                minIdx := 0
                if digitSumMap[s][1] < digitSumMap[s][0] {
                    minIdx = 1
                }
                digitSumMap[s] = digitSumMap[s][:2]
            }
        }
    }
    
    maxSum := -1
    for _, numbers := range digitSumMap {
        if len(numbers) >= 2 {
            if numbers[0]+numbers[1] > maxSum {
                maxSum = numbers[0] + numbers[1]
            }
        }
    }
    
    return maxSum
}

The Go implementation mirrors the Python approach. A helper function computes the digit sum. The hash map stores the largest two numbers per digit sum, and care is taken to sort or swap elements to maintain the largest two. The rest of the algorithm computes the maximum sum.

Worked Examples

Example 1: nums = [18,43,36,13,7]

num digit_sum digit_sum_map state
18 9 {9: [18]}
43 7 {9: [18], 7: [43]}
36 9 {9: [36,18], 7: [43]}
13 4 {9: [36,18], 7: [43], 4: [13]}
7 7 {9: [36,18], 7: [43,7], 4: [13]}

Max sums per group: 36+18=54, 43+7=50, 13 (only one). Maximum sum is 54.

Example 2: nums = [10,12,19,14]

All digit sums are unique: 1,3,10,5. No group has two numbers. Return -1.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each number is processed once. Digit sum computation is O(log(num)), which is bounded by 10 for max num 10^9, so effectively O(n).
Space O(n) The hash map stores up to 2 numbers for each digit sum, at most O(n) in total.

The algorithm is efficient because it avoids checking all pairs. Using a hash map ensures constant-time access for updating maximum pairs.

Test Cases

# Provided examples
assert Solution().maximumSum([18,43,36,13,7]) == 54  # max sum for digit sum 9
assert Solution().maximumSum([10,12,19,14]) == -1   # no valid pairs

# Single element
assert Solution().maximumSum([5]) == -1  # cannot form a pair

# Multiple pairs same digit sum
assert Solution().maximumSum([12,21,30,3]) == 42  # digit sum 3 -> max pair 12+30

# All same digit sum
assert Solution().maximumSum([11,20,2,101]) == 121  # max pair 20+101

# Large numbers
assert Solution().maximumSum([10**9, 10**9-1, 1]) == 1999999999  # digit sum 1e9 -> only two largest numbers
Test Why
[18,43,36,13,7] Tests normal case with multiple pairs
[10,12,19,14] Tests no valid pairs
[5] Tests single-element edge case
[12,21,30,3] Tests multiple numbers with same digit sum
[11,20,2,101] Tests all numbers with same digit sum
Large numbers Tests algorithm handles maximum values correctly

Edge Cases

One edge case is when the array contains only one number. No pair can be formed, so the function correctly returns -1. Another case is when multiple numbers have the same digit sum, but some are duplicates. The implementation handles duplicates because it considers the two largest numbers regardless of equality. A third edge case is when all numbers have unique digit sums, in which case the function returns -1. This is correctly handled because the algorithm only computes sums