Max Sum of a Pair With Equal Sum of Digits LeetCode solution in Python

1
class Solution:  # The plan here is to:
2
    #
3
    #   • sort the elements of nums into a dict of maxheaps,
4
    #     according to sum-of-digits.
5
    #
6
    #   • For each key, determine whether there are at least two
7
    #     elements in that key's values, and if so, compute the
8
    #     product of the greatest two elements.
9
    #
10
    #   • return the the greatest such product as the answer.
11

12
    # For example:
13

14
    #     nums = [6,15,13,12,24,21] –> {3:[12,21], 4:[13], 6:[6,15,24]}
15

16
    #     Only two keys qualify, 3 and 6, for which the greatest two elements
17
    #     are 12,21 and 15,24, respectively. 12+21 = 33 and 15+24 = 39,
18
    #     so the answer is 39.
19

20
    def maximumSum(self, nums: List[int]) -> int:
21
        d, mx = defaultdict(list), -1
22
        digits = lambda x: sum(map(int, list(str(x))))  # <-- sum-of-digits function
23

24
        for n in nums:  # <-- construct max-heaps
25
            heappush(d[digits(n)], -n)  #     (note "-n")
26

27
        for i in d:  # <-- pop the two greatest values off
28
            if len(d[i]) > 1:  #     each maxheap (when possible) and
29
                mx = max(
30
                    mx, -heappop(d[i]) - heappop(d[i])
31
                )  #     compare with current max value.
32

33
        return mx