array and hashmap September 11, 2022

Max sum of a pair with equal sum of digits

Time O(n) Space O(n) Open original problem

This problem is very similar to two sum problem. But instead of storing the complement of the number, we will store the sum of digits of the number. When we iterate over the numbers, we will also keep a running result for the max of the number pair. If we can't find any after the iteration is done, we return -1, otherwise we will return the running maximum.

class Solution:
    def maximumSum(self, nums: List[int]) -> int:
        res = -math.inf
        lookup = {}

        for num in nums:
            digitSum = sum([int(n) for n in str(num)])
            if digitSum not in lookup:
                lookup[digitSum] = num
            else:
                res = max(res, num+lookup[digitSum])
                lookup[digitSum] = max(lookup[digitSum], num)

        return res if res != -math.inf else -1

Time Complexity: O(n)
Space Complexity: O(n)