Linear time solution using "bucketization" approach

Easy problem which could have been solved in N^2 since N=100, but for a very large N, say N=10^6, a square solution would have been intractable.

Instead, make use of the "bucketization" approach:

1/ Have a bucket with 10 elements corresponding to the 10 available digits

2/ Each bucket element is actually the top two elements whose max digit is the bucket index

That way you can populate the bucket in N*Log(max number in nums), since the max number in nums is 10^4, you have a time complexity of N*Log(10^4), which would be 4N which would be a big O(N)-time complexity.

Code is down below, cheers, ACC.

Max Pair Sum in an Array - LeetCode

2815. Max Pair Sum in an Array

Easy

You are given a 0-indexed integer array nums. You have to find the maximum sum of a pair of numbers from nums such that the maximum digit in both numbers are equal.

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

 

Example 1:

Input: nums = [51,71,17,24,42]
Output: 88
Explanation: 
For i = 1 and j = 2, nums[i] and nums[j] have equal maximum digits with a pair sum of 71 + 17 = 88. 
For i = 3 and j = 4, nums[i] and nums[j] have equal maximum digits with a pair sum of 24 + 42 = 66.
It can be shown that there are no other pairs with equal maximum digits, so the answer is 88.

Example 2:

Input: nums = [1,2,3,4]
Output: -1
Explanation: No pair exists in nums with equal maximum digits.

 

Constraints:

• 2 <= nums.length <= 100
• 1 <= nums[i] <= 104

public int MaxSum(int[] nums)
{
    int[][] topPerDigit = new int[10][];

    for (int i = 0; i < topPerDigit.Length; i++) topPerDigit[i] = new int[2];

    foreach (int n in nums)
    {
        int temp = n;
        int maxDigit = -1;
        while (temp > 0)
        {
            int digit = temp % 10;
            maxDigit = Math.Max(maxDigit, digit);
            temp /= 10;
        }
        if (n > topPerDigit[maxDigit][0])
        {
            topPerDigit[maxDigit][1] = topPerDigit[maxDigit][0];
            topPerDigit[maxDigit][0] = n;
        }
        else if (n > topPerDigit[maxDigit][1])
        {
            topPerDigit[maxDigit][1] = n;
        }
    }

    int max = -1;
    for (int i = topPerDigit.Length - 1; i >= 0; i--)
    {
        if (topPerDigit[i][0] > 0 && topPerDigit[i][1] > 0)
        {
            max = Math.Max(max, topPerDigit[i][0] + topPerDigit[i][1]);
        }
    }
    return max;
}