Max Pair Sum in an Array

Easy
1805.

Max Pair Sum in an Array

Max Pair Sum in an Array is an easy coding problem on arrays and hash table, asked in Amazon interviews.

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 <= 100
  • 1 <= nums[i] <= 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSum = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 100
  • 1 <= nums[i] <= 10^4

Hints for Max Pair Sum in an Array

  1. Hint 1

    Group the numbers by their largest digit. Only numbers in the same group can pair.

  2. Hint 2

    Within a group, the best pair is simply its two largest numbers.

  3. 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

  1. Let best[d] = 0 for every digit d, and answer = -1.
  2. For each x, compute its largest digit d by peeling off digits with % 10.
  3. If best[d] > 0, set answer = max(answer, best[d] + x).
  4. Set best[d] = max(best[d], x). Return answer.

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 answer

Java

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