LeetCode 2815. Max Pair Sum in an Array Solution in Java, C++, Python & More | Explanation + Code

Description

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

Solutions

Solution 1: 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² × log M), where n is the length of the array and M is the maximum value in the array.

PythonJavaC++GoTypeScript

class Solution: def maxSum(self, nums: List[int]) -> int: ans = -1 for i, x in enumerate(nums): for y in nums[i + 1 :]: v = x + y if ans < v and max(str(x)) == max(str(y)): ans = v return ans(code-box)

class Solution { public int maxSum(int[] nums) { int ans = -1; int n = nums.length; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { int v = nums[i] + nums[j]; if (ans < v && f(nums[i]) == f(nums[j])) { ans = v; } } } return ans; } private int f(int x) { int y = 0; for (; x > 0; x /= 10) { y = Math.max(y, x % 10); } return y; } }(code-box)

class Solution { public: int maxSum(vector<int>& nums) { int ans = -1; int n = nums.size(); auto f = [](int x) { int y = 0; for (; x; x /= 10) { y = max(y, x % 10); } return y; }; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { int v = nums[i] + nums[j]; if (ans < v && f(nums[i]) == f(nums[j])) { ans = v; } } } return ans; } };(code-box)

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 }(code-box)

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; }(code-box)