We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Max Pair Sum in an Array

Difficulty: Easy

Problem Description

You are given an integer array nums. You have to find the maximum sum of a pair of numbers from nums such that the largest digit in both numbers is equal. Return the maximum sum or -1 if no such pair exists.

Key Insights

  • Each number can be analyzed to determine its largest digit.
  • We can group numbers based on their largest digit.
  • The maximum pair sum can be calculated for each group with the same largest digit.
  • If no pairs exist for any digit, return -1.

Space and Time Complexity

Time Complexity: O(n) - where n is the number of elements in the array. We traverse the list to find the largest digits and their associated numbers. Space Complexity: O(1) - we only use a fixed number of variables and a hash map to store sums, which does not depend on the input size.

Solution

To solve the problem, we will use a hash map (or dictionary) to group numbers by their largest digit. For each number, we will calculate its largest digit and store the numbers in the hash map. After populating the map, we will compute the maximum sum for each digit's group by checking the two largest numbers. If no valid pairs exist, we return -1.

Code Solutions

def max_pair_sum(nums):
    from collections import defaultdict
    
    # A dictionary to hold numbers grouped by their largest digit
    digit_map = defaultdict(list)
    
    # Helper function to find the largest digit in a number
    def largest_digit(n):
        return max(int(d) for d in str(n))
    
    # Populate the digit_map with numbers
    for num in nums:
        ld = largest_digit(num)
        digit_map[ld].append(num)
    
    max_sum = -1
    
    # Calculate maximum pair sums for each digit group
    for numbers in digit_map.values():
        if len(numbers) > 1:
            numbers.sort(reverse=True)  # Sort to get the largest two numbers
            pair_sum = numbers[0] + numbers[1]
            max_sum = max(max_sum, pair_sum)
    
    return max_sum
← Back to All Questions