Max Pair Sum in an Array solution and explanation
Google
9 more videos on this problem
Max Pair Sum in an Array | Leetcode 2815 | Hashing | C++Tech Courses · 7:41 · 1K views
Leetcode | 2815. Max Pair Sum in an Array | Easy | Java SolutionDeveloper Docs · 3:47 · 1K views
Leetcode Weekly contest 358 - Easy - Max Pair Sum in an ArrayPrakhar Agrawal · 3:52 · 942 views
LeetCode 2815 - Max Pair Sum in an Array ( Naive Approach ) | Problem Solving | LeetCodeAlmighty Tricks · 9:03 · 940 views
Leetcode 2815 Max Pair Sum in an Array | Beats 100%Tech Diet · 5:58 · 521 views
2815. Max Pair Sum in an Array || Weekly Contest 358 || Leetcode || HindiAshish Kumar · 3:38 · 487 views
2815. Max Pair Sum in an Array (Leetcode Easy)Programming Live with Larry · 3:49 · 443 views
# leetcode 358th Max pair sum in an array #leetcodechallengecrazy developers · 0:21 · 372 views
LeetCode 2815 : Max Pair Sum in an Array || EASY || C++ || JAVA || Detailed SolutionCodeGPT · 12:36 · 369 views
Ultimate LeetCode 2815. Max Pair Sum in an Array + LIVE CODING in PythonvanAmsen · 6:17 · 211 views
The 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.
Example 1:
Input: nums = [112,131,411]
Output: -1
Explanation:
Each numbers largest digit in order is [2,3,4].
Example 2:
Input: nums = [2536,1613,3366,162]
Output: 5902
Explanation:
All the numbers have 6 as their largest digit, so the answer is 2536 + 3366 = 5902.
Example 3:
Input: nums = [51,71,17,24,42]
Output: 88
Explanation:
Each number's largest digit in order is [5,7,7,4,4].
So we have only two possible pairs, 71 + 17 = 88 and 24 + 42 = 66.
Constraints:
2 <= nums.length <= 1001 <= nums[i] <= 104
Approach overview
Problem Overview: You are given an integer array and must find the maximum sum of a pair of numbers where both numbers share the same highest digit. If no such pair exists, return -1. The key observation is that numbers can only form a valid pair if their largest digit (0–9) matches.
Approach 1: HashMap-Based Approach (O(n) time, O(1) space)
Scan the array once and compute the maximum digit of each number. Use a hash map (or fixed array of size 10) where the key is the maximum digit and the value stores the largest number seen so far with that digit. For each new number, check if another number with the same maximum digit already exists. If it does, compute the pair sum and update the global maximum. Then update the stored value if the current number is larger. Each element is processed once and digit extraction is constant time, giving O(n) time and O(1) extra space since the digit range is fixed.
This approach relies on quick lookups using a hash table and simple iteration over the array. It works well because the grouping condition (maximum digit) has only 10 possible values.
Approach 2: Sort and Two-Pointers Approach (O(n log n) time, O(1) extra space)
Another option is to sort the array in descending order and compare numbers with the same maximum digit. After sorting, compute the largest digit for each number and group or scan adjacent candidates that share the same digit. Because larger numbers appear first, the first valid pair encountered for a digit often produces the maximum sum. Sorting costs O(n log n), and scanning afterward is linear.
This method uses sorting and sometimes a two pointers style scan to evaluate candidate pairs efficiently. It is easier to reason about when you want the largest values considered first, but it is slower than the hash map solution due to the sorting step.
Recommended for interviews: The hash map approach is the expected optimal solution. It shows that you recognized the constraint that the maximum digit ranges only from 0–9 and used that to group numbers efficiently. Brute-force pair checking would take O(n^2), which demonstrates basic understanding, but the O(n) hash-based grouping shows stronger problem-solving skills.
Approach 1: HashMap-Based Approach
This approach involves using a HashMap to group numbers by their largest digit. The key idea is to find the largest digit in each number and use this digit as a key in the HashMap. For each group (specific largest digit), try to find two numbers that sum to the maximum value. If no such pair exists, return -1.
def max_pair_sum(nums):
max_sums = {}
max_total = -1
for num in nums:
max_digit = max(int(d) for d in str(num))
if max_digit in max_sums:
max_total = max(max_total, max_sums[max_digit] + num)
max_sums[max_digit] = max(max_sums[max_digit], num)
else:
max_sums[max_digit] = num
return max_total
nums = [2536, 1613, 3366, 162]
print(max_pair_sum(nums))import java.util.HashMap;
public class MaxPairSum {
public static int maxPairSum(int[] nums) {
HashMap<Integer, Integer> map = new HashMap<>();
int maxSum = -1;
for (int num : nums) {
int maxDigit = 0, n = num;
while (n > 0) {
maxDigit = Math.max(maxDigit, n % 10);
n /= 10;
}
if (map.containsKey(maxDigit)) {
maxSum = Math.max(maxSum, map.get(maxDigit) + num);
map.put(maxDigit, Math.max(map.get(maxDigit), num));
} else {
map.put(maxDigit, num);
}
}
return maxSum;
}
public static void main(String[] args) {
int[] nums = {2536, 1613, 3366, 162};
System.out.println(maxPairSum(nums));
}
}#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
int maxPairSum(vector<int>& nums) {
unordered_map<int, int> maxSum;
for (const auto& num : nums) {
int n = num, largestDigit = 0;
while (n > 0) {
largestDigit = max(largestDigit, n % 10);
n /= 10;
}
if (maxSum.count(largestDigit)) {
maxSum[largestDigit] = max(maxSum[largestDigit], maxSum[largestDigit] + num);
} else {
maxSum[largestDigit] = num;
}
}
int result = -1;
for (const auto& [digit, sum] : maxSum) {
result = max(result, sum);
}
return result;
}
int main() {
vector<int> nums = {2536, 1613, 3366, 162};
cout << maxPairSum(nums) << endl;
return 0;
}function maxPairSum(nums) {
const maxSums = {};
let maxSum = -1;
for (const num of nums) {
const maxDigit = Math.max(...num.toString().split('').map(Number));
if (maxDigit in maxSums) {
maxSum = Math.max(maxSum, maxSums[maxDigit] + num);
maxSums[maxDigit] = Math.max(maxSums[maxDigit], num);
} else {
maxSums[maxDigit] = num;
}
}
return maxSum;
}
console.log(maxPairSum([2536, 1613, 3366, 162]));#include <stdio.h>
#include <stdlib.h>
int maxPairSum(int* nums, int numsSize) {
int *maxSums = calloc(10, sizeof(int));
for (int i = 0; i < numsSize; i++) {
int num = nums[i], maxDigit = 0, temp = num;
while (temp > 0) {
maxDigit = (temp % 10 > maxDigit) ? temp % 10 : maxDigit;
temp /= 10;
}
if (maxSums[maxDigit] > 0) {
maxSums[maxDigit] = (maxSums[maxDigit] + num > maxSums[maxDigit]) ? maxSums[maxDigit] + num : maxSums[maxDigit];
} else {
maxSums[maxDigit] = num;
}
}
int result = -1;
for (int i = 0; i < 10; i++) {
if (maxSums[i] > result) {
result = maxSums[i];
}
}
free(maxSums);
return result;
}
int main() {
int nums[] = {2536, 1613, 3366, 162};
int result = maxPairSum(nums, 4);
printf("%d\n", result);
return 0;
}using System;
using System.Collections.Generic;
class MaxPairSumProgram {
static int MaxPairSum(int[] nums) {
Dictionary<int, int> maxDigits = new Dictionary<int, int>();
int result = -1;
foreach (int num in nums) {
int n = num, maxDigit = 0;
while (n > 0) {
maxDigit = Math.Max(maxDigit, n % 10);
n /= 10;
}
if (maxDigits.TryGetValue(maxDigit, out int existingMax)) {
result = Math.Max(result, existingMax + num);
maxDigits[maxDigit] = Math.Max(existingMax, num);
} else {
maxDigits[maxDigit] = num;
}
}
return result;
}
static void Main() {
int[] nums = {2536, 1613, 3366, 162};
Console.WriteLine(MaxPairSum(nums));
}
}Python's dynamic typing and dictionary make implementing this approach straightforward. Convert numbers to strings to easily extract digits. The dictionary keeps track of the highest number with a specific largest digit. The max sum found is updated if possible, and finally returned if any valid pairs exist.
Time Complexity: O(n). Iterate through nums and manage a dictionary efficiently.
Space Complexity: O(1). Similarly, count of unique digits is bounded by 10.
Approach 2: Sort and Two-Pointers Approach
This approach sorts numbers based on their largest digit and then uses a two-pointer technique to find the maximum sum of numbers with the same largest digit. While straightforward, it assumes a sorting cost, thus this might be less efficient than a pure HashMap solution.
def max_pair_sum(nums):
def max_digit(num):
return max(int(d) for d in str(num))
nums.sort(key=lambda x: -max_digit(x))
max_sum = -1
for i in range(len(nums) - 1):
if max_digit(nums[i]) == max_digit(nums[i + 1]):
max_sum = max(max_sum, nums[i] + nums[i + 1])
return max_sum
nums = [2536, 1613, 3366, 162]
print(max_pair_sum(nums))import java.util.Arrays;
public class MaxPairSum {
private static int maxDigit(int num) {
int maxDigit = 0;
while (num > 0) {
maxDigit = Math.max(maxDigit, num % 10);
num /= 10;
}
return maxDigit;
}
public static int maxPairSum(int[] nums) {
Arrays.sort(nums, (a, b) -> maxDigit(b) - maxDigit(a));
int maxSum = -1;
for (int i = 0; i < nums.length - 1; i++) {
if (maxDigit(nums[i]) == maxDigit(nums[i + 1])) {
int sum = nums[i] + nums[i + 1];
maxSum = Math.max(maxSum, sum);
}
}
return maxSum;
}
public static void main(String[] args) {
int[] nums = {2536, 1613, 3366, 162};
System.out.println(maxPairSum(nums));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int getMaxDigit(int num) {
int maxDigit = 0;
while (num > 0) {
maxDigit = max(maxDigit, num % 10);
num /= 10;
}
return maxDigit;
}
int maxPairSum(vector<int>& nums) {
sort(nums.begin(), nums.end(), [](int a, int b) {
return getMaxDigit(a) > getMaxDigit(b);
});
int maxSum = -1;
for (size_t i = 1; i < nums.size(); ++i) {
if (getMaxDigit(nums[i]) == getMaxDigit(nums[i-1])) {
maxSum = max(maxSum, nums[i] + nums[i-1]);
}
}
return maxSum;
}
int main() {
vector<int> nums = {2536, 1613, 3366, 162};
cout << maxPairSum(nums) << endl;
return 0;
}function maxPairSum(nums) {
nums.sort((a, b) => {
const maxDigitA = Math.max(...a.toString().split('').map(Number));
const maxDigitB = Math.max(...b.toString().split('').map(Number));
return maxDigitB - maxDigitA;
});
let maxSum = -1;
for (let i = 0; i < nums.length - 1; i++) {
if (Math.max(...nums[i].toString()) === Math.max(...nums[i + 1].toString())) {
maxSum = Math.max(maxSum, nums[i] + nums[i + 1]);
}
}
return maxSum;
}
console.log(maxPairSum([2536, 1613, 3366, 162]));#include <stdio.h>
#include <stdlib.h>
int getMaxDigit(int num) {
int maxDigit = 0;
while (num > 0) {
maxDigit = (num % 10 > maxDigit) ? num % 10 : maxDigit;
num /= 10;
}
return maxDigit;
}
int cmpfunc(const void *a, const void *b) {
return getMaxDigit(*(int *)b) - getMaxDigit(*(int *)a);
}
int maxPairSum(int* nums, int numsSize) {
qsort(nums, numsSize, sizeof(int), cmpfunc);
int maxSum = -1;
for (int i = 0; i < numsSize - 1; i++) {
for (int j = i + 1; j < numsSize; j++) {
if (getMaxDigit(nums[i]) == getMaxDigit(nums[j])) {
int tempSum = nums[i] + nums[j];
if (tempSum > maxSum) {
maxSum = tempSum;
}
}
}
}
return maxSum;
}
int main() {
int nums[] = {2536, 1613, 3366, 162};
int result = maxPairSum(nums, 4);
printf("%d\n", result);
return 0;
}using System;
using System.Linq;
class MaxPairSumProgram {
static int MaxDigit(int num) {
int maxDigit = 0;
while (num > 0) {
maxDigit = Math.Max(maxDigit, num % 10);
num /= 10;
}
return maxDigit;
}
static int MaxPairSum(int[] nums) {
Array.Sort(nums, (a, b) => MaxDigit(b).CompareTo(MaxDigit(a)));
int maxSum = -1;
for (int i = 0; i < nums.Length - 1; i++) {
if (MaxDigit(nums[i]) == MaxDigit(nums[i + 1])) {
maxSum = Math.Max(maxSum, nums[i] + nums[i + 1]);
}
}
return maxSum;
}
static void Main() {
int[] nums = {2536, 1613, 3366, 162};
Console.WriteLine(MaxPairSum(nums));
}
}This Python solution leverages sorting with a key function to organize numbers by their largest digit. The two-pointer-like logic is next used to find potential max sum pairs post sorting.
Time Complexity: O(n log n) caused by the sort.
Space Complexity: O(n) required by sorting algorithms for lists.
Approach 3: Enumeration
First, we initialize the answer variable ans=-1. Next, we directly enumerate all pairs (nums[i], nums[j]) where i \lt j, and calculate their sum v=nums[i] + nums[j]. If v is greater than ans and the largest digit of nums[i] and nums[j] are the same, then we update ans with v.
The time complexity is O(n^2 times log M), where n is the length of the array and M is the maximum value in the array.
function maxSum(nums: number[]): number {
const n = nums.length;
let ans = -1;
const f = (x: number): number => {
let y = 0;
for (; x > 0; x = Math.floor(x / 10)) {
y = Math.max(y, x % 10);
}
return y;
};
for (let i = 0; i < n; ++i) {
for (let j = i + 1; j < n; ++j) {
const v = nums[i] + nums[j];
if (ans < v && f(nums[i]) === f(nums[j])) {
ans = v;
}
}
}
return ans;
}func maxSum(nums []int) int {
ans := -1
f := func(x int) int {
y := 0
for ; x > 0; x /= 10 {
y = max(y, x%10)
}
return y
}
for i, x := range nums {
for _, y := range nums[i+1:] {
if v := x + y; ans < v && f(x) == f(y) {
ans = v
}
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| HashMap-Based Approach | Time Complexity: O(n). Iterate through nums and manage a dictionary efficiently. |
| Sort and Two-Pointers Approach | Time Complexity: O(n log n) caused by the sort. |
| Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap-Based Grouping by Max Digit | O(n) | O(1) | Best general solution. Efficient when grouping elements by a small fixed key range (digits 0–9). |
| Sort and Two-Pointers Scan | O(n log n) | O(1) | Useful when working with sorted arrays or when you want the largest candidates evaluated first. |
Frequently asked questions
Is Max Pair Sum in an Array easy or hard?
Max Pair Sum in an Array is classified as an Easy problem on LeetCode with an acceptance rate of about 60%. The main challenge is recognizing that numbers should be grouped by their maximum digit and solved efficiently with a hash map rather than checking every possible pair.
Max Pair Sum in an Array Python/Java solution
In Python or Java, the typical solution computes the maximum digit of each number and stores the best value for that digit in a dictionary or HashMap. Each new number checks the map to form a pair and update the maximum sum. The algorithm runs in O(n) time and uses constant extra space.
How to solve Max Pair Sum in an Array in O(n)?
Iterate through the array and compute the maximum digit of each number. Maintain a hash map where the key is the maximum digit and the value is the largest number seen with that digit. If another number with the same digit appears, compute the pair sum and update the result. This single pass keeps the complexity at O(n).
What is the best approach for Max Pair Sum in an Array?
The optimal approach groups numbers by their maximum digit using a hash map. While scanning the array, store the largest value seen for each digit and update the maximum pair sum when another number with the same digit appears. This method runs in O(n) time and uses O(1) space because the digit range is limited to 0–9.
Is Max Pair Sum in an Array asked at Google/Amazon/Meta?
Variants of this problem appear in interviews at companies like Amazon and Google where candidates must group elements based on a derived property and compute optimal pairs. It tests array processing, hash table usage, and recognizing constrained key spaces.
What data structure is used in Max Pair Sum in an Array?
A hash table (or a fixed array of size 10) is used to group numbers by their maximum digit. This allows constant-time lookups to check whether a previous number with the same digit already exists and quickly compute candidate pair sums.
What is the time complexity of Max Pair Sum in an Array?
The optimal hash map solution runs in O(n) time because each number is processed once and digit extraction takes constant time. Space complexity is O(1) since only up to 10 buckets are required for digits 0 through 9. A sorting-based alternative takes O(n log n) time.