Max Pair Sum in an Array

Max Pair Sum in an Array - Problem

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.

For example, 2373 is made up of three distinct digits: 2, 3, and 7, where 7 is the largest among them.

Return the maximum sum or -1 if no such pair exists.

Input & Output

Example 1 — Basic Case

$ Input: nums = [58, 18, 85, 56]

› Output: 141

💡 Note: Numbers with max digit 8: [58, 18, 85]. Best pair is 85 + 56 = 141. Wait, 56 has max digit 6, so we pair within max digit 8: 85 + 58 = 143. Actually, let me recalculate: 85 + 58 = 143 (both have max digit 8).

Example 2 — No Valid Pairs

$ Input: nums = [1, 23, 456]

› Output: -1

💡 Note: Max digits are 1, 3, and 6 respectively. No two numbers share the same max digit, so return -1.

Example 3 — Multiple Groups

$ Input: nums = [12, 34, 56, 78, 19, 29]

› Output: 107

💡 Note: Max digits: [2,4,6,8,9,9]. Numbers with max digit 9: [19,29]. Sum: 19 + 29 = 48. All other max digits appear only once, so maximum sum is 48.

Constraints

2 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁶

Visualization

Tap to expand

Asked in

G Google 25 a Amazon 20 M Microsoft 18 Apple 15

The key insight is that only numbers sharing the same largest digit can form valid pairs. The optimal approach uses a single-pass algorithm tracking the two largest numbers for each max digit. Best approach: Single Pass Hash Map - Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map Grouping	O(n log n)	O(n)	Group numbers by their largest digit and find maximum sum within each group
Single Pass with Hash Map	O(n)	O(1)	Track the two largest numbers for each max digit in a single pass
Brute Force	O(n²)	O(1)	Check all possible pairs and find maximum sum where both numbers have same largest digit

Hash Map Grouping — Algorithm Steps

Calculate largest digit for each number
Group numbers by their largest digit in hash map
For each group with 2+ numbers, find two largest
Return maximum sum found or -1

Visualization

Tap to expand

Step-by-Step Walkthrough

Extract Max Digits

Find largest digit in each number

Group by Digit

Create groups for each max digit

Find Best Pairs

Get two largest from each group

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int getMaxDigit(int num) {
    int maxDigit = 0;
    num = abs(num);
    while (num > 0) {
        int digit = num % 10;
        if (digit > maxDigit) maxDigit = digit;
        num /= 10;
    }
    return maxDigit;
}

int compare(const void* a, const void* b) {
    return (*(int*)b - *(int*)a);
}

int solution(int* nums, int n) {
    // Simple approach: for each digit 0-9, collect numbers with that max digit
    int groups[10][100];
    int groupSizes[10] = {0};
    
    // Group numbers by their largest digit
    for (int i = 0; i < n; i++) {
        int maxDigit = getMaxDigit(nums[i]);
        groups[maxDigit][groupSizes[maxDigit]++] = nums[i];
    }
    
    int maxSum = -1;
    
    // For each group, find the two largest numbers
    for (int digit = 0; digit <= 9; digit++) {
        if (groupSizes[digit] >= 2) {
            qsort(groups[digit], groupSizes[digit], sizeof(int), compare);
            int currentSum = groups[digit][0] + groups[digit][1];
            if (currentSum > maxSum) maxSum = currentSum;
        }
    }
    
    return maxSum;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[100], n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        int val = atoi(token);
        if (val != 0 || token[0] == '0') {
            nums[n++] = val;
        }
        token = strtok(NULL, "[,]");
    }
    
    printf("%d\n", solution(nums, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

O(n) to group numbers, O(k log k) to sort each group where k is average group size

⚡ Linearithmic

Space Complexity

O(n)

Hash map stores all n numbers grouped by max digit

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map Grouping — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler