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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Max Pair Sum in an Array

Number: 2902

Difficulty: Easy

Paid? No

Companies: Google, Microsoft

Problem Description

Given an integer array nums, find the maximum sum of a pair of numbers such that the largest digit (when considering each number's digits) in both numbers is the same. If no such pair exists, return -1.

Key Insights

  • The largest digit for a number can be derived by examining all its digits.
  • Group the numbers by their largest digit.
  • For each group, maintain the top two largest numbers to compute the potential maximum pair sum.
  • If a group has fewer than two numbers, ignore that group.
  • Finally, choose the maximum sum among all valid groups.

Space and Time Complexity

Time Complexity: O(n * d) where n is the number of elements and d is the number of digits per number (constant-time operation given the input constraints). Space Complexity: O(n), to store the grouping of numbers based on their largest digit.

Solution

The solution involves the following steps:

  1. Iterate through each number in the array.
  2. For each number, determine the largest digit by converting the number to a string and checking each digit.
  3. Group numbers by this largest digit. For each group, keep track of the top two largest numbers.
  4. Iterate over the groups and calculate the sum of the top two numbers for each group (if available).
  5. Return the maximum sum found or -1 if no valid pair exists.

The main data structure used is a hash table (or dictionary) to map each largest digit to a pair of its highest numbers. This approach simplifies grouping and efficient pair selection while ensuring we meet the problem constraints.

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java with line-by-line comments.

# Function to find the largest digit in a number
def get_largest_digit(num):
    # Convert the number to string to iterate each digit and get the maximum
    return int(max(str(num)))

def max_pair_sum(nums):
    # Dictionary to store the top two numbers for each largest digit key
    digit_groups = {}
    
    # Iterate over each number in the given list
    for num in nums:
        # Get largest digit of the current number
        largest_digit = get_largest_digit(num)
        
        # If this largest digit is not already a key, initialize it with an empty list
        if largest_digit not in digit_groups:
            digit_groups[largest_digit] = []
        
        # Add the current number into the group list
        digit_groups[largest_digit].append(num)
    
    max_sum = -1
    # Iterate over each group in the dictionary
    for group in digit_groups.values():
        # Only consider groups with two or more numbers
        if len(group) >= 2:
            # Sort the group in descending order to get the two largest numbers at beginning
            group.sort(reverse=True)
            # Calculate the sum of the two largest numbers
            current_sum = group[0] + group[1]
            # Update max_sum if current_sum is larger
            max_sum = max(max_sum, current_sum)
            
    return max_sum

# Example usage
if __name__ == "__main__":
    print(max_pair_sum([2536,1613,3366,162]))  # Output: 5902
← Back to All Questions