Problem Description

You are given an integer array nums. Your task is to find the maximum sum of a pair of numbers from this array, with a special condition: both numbers in the pair must have the same largest digit.

To understand what "largest digit" means, consider the number 2373. This number contains the digits 2, 3, 7, and 3. Among these digits, 7 is the largest.

Here's what you need to do:

• Find all possible pairs of numbers from the array
• For each pair, check if both numbers have the same largest digit
• If they do, calculate their sum
• Return the maximum sum among all valid pairs

If no pair exists where both numbers have the same largest digit, return -1.

For example:

• If nums = [51, 71, 17, 42]
  • 51 has largest digit 5
  • 71 has largest digit 7
  • 17 has largest digit 7
  • 42 has largest digit 4
  • The pairs (71, 17) both have largest digit 7, so their sum 71 + 17 = 88 would be a valid candidate
  • Since this is the only valid pair, the answer would be 88

Intuition

When we need to find the maximum sum of a pair with a specific constraint, the most straightforward approach is to check all possible pairs. Since we're looking for a maximum value and have a filtering condition (same largest digit), a brute force approach makes sense here.

The key insight is that we need to:

1. Compare every possible pair of numbers in the array
2. For each pair, determine if they meet our condition (same largest digit)
3. Keep track of the maximum sum we've seen so far

To find the largest digit in a number, we can convert the number to a string and use the max() function on the string representation. For example, max(str(2373)) would give us '7', which is exactly what we need.

The nested loop structure naturally emerges from the need to examine all pairs. For each number at position i, we check it against all numbers that come after it (positions i+1 to the end). This ensures we don't count the same pair twice and don't pair a number with itself.

We start with ans = -1 to handle the case where no valid pairs exist. As we find valid pairs (those with matching largest digits), we update ans only when we find a larger sum. This way, we're guaranteed to end up with either the maximum sum or -1 if no valid pairs were found.

The beauty of this approach lies in its simplicity - we're directly implementing what the problem asks for without any complex data structures or algorithms.

Solution Approach

The solution uses a brute force enumeration approach to check all possible pairs in the array.

We start by initializing ans = -1 to handle the case where no valid pair exists.

The implementation uses two nested loops to generate all pairs:

• The outer loop iterates through each element with its index: for i, x in enumerate(nums)
• The inner loop iterates through all elements after position i: for y in nums[i + 1:]

This ensures we check each unique pair exactly once without duplicates.

For each pair (x, y):

1. Calculate the sum: v = x + y
2. Check if this sum is greater than our current answer: ans < v
3. Check if both numbers have the same largest digit: max(str(x)) == max(str(y))
   • Converting to string allows us to easily access individual digits
   • The max() function on a string returns the character with the highest ASCII value, which for digit characters corresponds to the largest digit

If both conditions are met (the sum is larger than our current best AND the largest digits match), we update our answer: ans = v

After checking all pairs, we return ans, which will either be:

• The maximum sum of a valid pair, or
• -1 if no pair with matching largest digits was found

The time complexity is O(n² × d) where n is the length of the array and d is the average number of digits in the numbers (for the string conversion and max digit finding). The space complexity is O(d) for the string conversions.

Example Walkthrough

Let's walk through the solution with nums = [84, 91, 18, 59, 27].

First, we initialize ans = -1 to handle the case where no valid pairs exist.

Now we'll check all possible pairs:

Pair (84, 91): i=0, x=84, y=91

• Sum: v = 84 + 91 = 175
• Is 175 > -1? Yes
• Largest digit of 84: max("84") = '8'
• Largest digit of 91: max("91") = '9'
• Do they match? No (8 ≠ 9)
• Don't update ans

Pair (84, 18): i=0, x=84, y=18

• Sum: v = 84 + 18 = 102
• Is 102 > -1? Yes
• Largest digit of 84: max("84") = '8'
• Largest digit of 18: max("18") = '8'
• Do they match? Yes (8 = 8)
• Update ans = 102

Pair (84, 59): i=0, x=84, y=59

• Sum: v = 84 + 59 = 143
• Is 143 > 102? Yes
• Largest digit of 84: max("84") = '8'
• Largest digit of 59: max("59") = '9'
• Do they match? No (8 ≠ 9)
• Don't update ans

Pair (84, 27): i=0, x=84, y=27

• Sum: v = 84 + 27 = 111
• Is 111 > 102? Yes
• Largest digit of 84: max("84") = '8'
• Largest digit of 27: max("27") = '7'
• Do they match? No (8 ≠ 7)
• Don't update ans

Pair (91, 18): i=1, x=91, y=18

• Sum: v = 91 + 18 = 109
• Is 109 > 102? Yes
• Largest digit of 91: max("91") = '9'
• Largest digit of 18: max("18") = '8'
• Do they match? No (9 ≠ 8)
• Don't update ans

Pair (91, 59): i=1, x=91, y=59

• Sum: v = 91 + 59 = 150
• Is 150 > 102? Yes
• Largest digit of 91: max("91") = '9'
• Largest digit of 59: max("59") = '9'
• Do they match? Yes (9 = 9)
• Update ans = 150

Pair (91, 27): i=1, x=91, y=27

• Sum: v = 91 + 27 = 118
• Is 118 > 150? No
• Skip checking (sum not greater than current ans)

Pair (18, 59): i=2, x=18, y=59

• Sum: v = 18 + 59 = 77
• Is 77 > 150? No
• Skip checking

Pair (18, 27): i=2, x=18, y=27

• Sum: v = 18 + 27 = 45
• Is 45 > 150? No
• Skip checking

Pair (59, 27): i=3, x=59, y=27

• Sum: v = 59 + 27 = 86
• Is 86 > 150? No
• Skip checking

After checking all pairs, we return ans = 150, which is the maximum sum of a pair where both numbers have the same largest digit (91 and 59, both with largest digit 9).

Solution Implementation

Time and Space Complexity

Time Complexity: O(n^2 × log M), where n is the length of the array and M is the maximum value in the array.

The analysis breaks down as follows:

• The outer loop iterates through all elements: O(n)
• The inner loop iterates through remaining elements after index i: O(n) in worst case
• For each pair of numbers (x, y), we compute max(str(x)) and max(str(y)):
  • Converting a number to string takes O(log M) time where M is the value of the number (number of digits is proportional to log M)
  • Finding the maximum character in the string also takes O(log M) time
• Therefore, the total time complexity is O(n × n × log M) = O(n^2 × log M)

Space Complexity: O(log M), where M is the maximum value in the array.

The space analysis:

• The variable ans uses O(1) space
• The loop variables i, x, y, and v use O(1) space
• The string conversion str(x) and str(y) create temporary strings of length O(log M)
• No additional data structures are used
• Therefore, the total space complexity is O(log M)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Inefficient Repeated Digit Extraction

The current solution converts numbers to strings and finds the maximum digit for every pair comparison. This means if a number appears in multiple pairs, we're recalculating its maximum digit repeatedly.

Problem Example: For an array like [51, 71, 17, 42, 51, 61], the number 51's maximum digit is calculated multiple times when it's paired with different numbers.

Solution: Pre-compute and cache the maximum digit for each number before checking pairs:

class Solution:
    def maxSum(self, nums: List[int]) -> int:
        # Pre-compute maximum digit for each number
        max_digits = {}
        for num in nums:
            max_digits[num] = max(str(num))
      
        max_sum = -1
        for i, first_num in enumerate(nums):
            for second_num in nums[i + 1:]:
                current_sum = first_num + second_num
                # Use cached values instead of recalculating
                if current_sum > max_sum and max_digits[first_num] == max_digits[second_num]:
                    max_sum = current_sum
      
        return max_sum

2. Suboptimal Algorithm for Large Arrays

The O(n²) approach becomes inefficient for large arrays when many numbers share the same maximum digit.

Problem Example: If most numbers have maximum digit 9, we're checking many unnecessary pairs and keeping only the maximum sum.

Optimized Solution: Group numbers by their maximum digit and only find the two largest numbers in each group:

class Solution:
    def maxSum(self, nums: List[int]) -> int:
        # Group numbers by their maximum digit
        digit_groups = {}
        for num in nums:
            max_digit = max(str(num))
            if max_digit not in digit_groups:
                digit_groups[max_digit] = []
            digit_groups[max_digit].append(num)
      
        max_sum = -1
        # For each group, find the sum of two largest numbers
        for group in digit_groups.values():
            if len(group) >= 2:
                group.sort(reverse=True)
                max_sum = max(max_sum, group[0] + group[1])
      
        return max_sum

This reduces time complexity to O(n log n) in the worst case (when all numbers have the same maximum digit and need sorting).