Max Pair Sum in an Array — Solution in Python, Java & C++
Max Pair Sum in an Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at Amazon.
Max Pair Sum in an Array is an easy coding problem on arrays and hash table, asked in Amazon interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an integer array nums. Choose two numbers at different indices whose largest digits are equal — for example 2373 and 3714 both have largest digit 7.
Return the maximum sum of such a pair, or -1 if no pair qualifies.
Example 1
Input: nums = [112,131,411]
Output: -1
Explanation: The largest digits are 2, 3 and 4 — all different.
Example 2
Input: nums = [2536,1613,3366,162]
Output: 5902
Explanation: 2536 and 3366 both have largest digit 6, and their sum 5902 beats every other qualifying pair.
Example 3
Input: nums = [51,71,17,24,42]
Output: 88
Explanation: 71 and 17 share the largest digit 7.
Constraints
2 <= nums.length <= 1001 <= nums[i] <= 10^4
Hints for Max Pair Sum in an Array
Hint 1
Group the numbers by their largest digit. Only numbers in the same group can pair.
Hint 2
Within a group, the best pair is simply its two largest numbers.
Hint 3
In one pass, keep for every digit 0–9 the largest number seen so far with that largest digit. Each new number tries to pair with that stored value before possibly replacing it.
How to solve Max Pair Sum in an Array
There are only ten possible largest digits. For each, the best pair is the two largest numbers in that group, which a single pass with a ten-slot array of running maxima finds.
Approach
- Let
best[d] = 0for every digitd, andanswer = -1. - For each
x, compute its largest digitdby peeling off digits with% 10. - If
best[d] > 0, setanswer = max(answer, best[d] + x). - Set
best[d] = max(best[d], x). Returnanswer.
Why it works
When x arrives, pairing it with the largest earlier member of its group is the best pair that has x as its later element; every pair is considered when its later element arrives, so the maximum over all x is the maximum over all pairs.
Complexity
- Time —
O(n · log10(max)) - Space —
O(1)
Pitfalls
- A pair needs two different indices — compare against the stored maximum before updating it with
x. - Return
-1(not 0) when no group has two members.
Reference solution
Python
from typing import List
def maxSum(nums: List[int]) -> int:
best = [0] * 10
answer = -1
for x in nums:
d = max(int(c) for c in str(x))
if best[d] > 0:
answer = max(answer, best[d] + x)
best[d] = max(best[d], x)
return answerJava
public static int maxSum(int[] nums) {
int[] best = new int[10];
int answer = -1;
for (int x : nums) {
int d = 0;
for (int t = x; t > 0; t /= 10) d = Math.max(d, t % 10);
if (best[d] > 0) answer = Math.max(answer, best[d] + x);
best[d] = Math.max(best[d], x);
}
return answer;
}C++
int maxSum(vector<int>& nums) {
int best[10] = {0};
int answer = -1;
for (int x : nums) {
int d = 0;
for (int t = x; t > 0; t /= 10) d = max(d, t % 10);
if (best[d] > 0) answer = max(answer, best[d] + x);
best[d] = max(best[d], x);
}
return answer;
}JavaScript
var maxSum = function(nums) {
var best = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
var answer = -1;
for (var i = 0; i < nums.length; i++) {
var x = nums[i], d = 0, t = x;
while (t > 0) { if (t % 10 > d) d = t % 10; t = Math.floor(t / 10); }
if (best[d] > 0 && best[d] + x > answer) answer = best[d] + x;
if (x > best[d]) best[d] = x;
}
return answer;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets