Jobs

Interviews

Discussions

Max Pair Sum in an Array

Easy

Amazon

3 views

Topics:

Arrays

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.

For example:

nums = [112,131,411]

In this case, the numbers' largest digits are [2, 3, 4]. Since no two numbers have the same largest digit, the answer is -1.

Another example:

nums = [2536,1613,3366,162]

All the numbers have 6 as their largest digit, so we choose the two numbers that give the largest sum: 2536 + 3366 = 5902.

Lastly:

nums = [51,71,17,24,42]

Here, the numbers' largest digits are [5, 7, 7, 4, 4]. So we have two possible pairs: 71 + 17 = 88 and 24 + 42 = 66. The result is the maximum of the two, which is 88.

Write a function that satisfies this requirement.

Max Pair Sum in an Array

Easy

Amazon

3 views

Topics:

Arrays

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.

For example:

nums = [112,131,411]

In this case, the numbers' largest digits are [2, 3, 4]. Since no two numbers have the same largest digit, the answer is -1.

Another example:

nums = [2536,1613,3366,162]

All the numbers have 6 as their largest digit, so we choose the two numbers that give the largest sum: 2536 + 3366 = 5902.

Lastly:

nums = [51,71,17,24,42]

Here, the numbers' largest digits are [5, 7, 7, 4, 4]. So we have two possible pairs: 71 + 17 = 88 and 24 + 42 = 66. The result is the maximum of the two, which is 88.

Write a function that satisfies this requirement.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of possible values for the integers in the array? Can I expect negative numbers?
What should I return if the array has fewer than two elements?
If there are multiple pairs with the same maximum sum, can I return any one of them?
Does the array contain duplicate numbers, and if so, should I consider them as distinct elements when finding the maximum pair sum?
Can the input array be empty or null? If so, what should I return?

Brute Force Solution

Approach

The brute force strategy for finding the maximum pair sum involves checking every single possible pair of numbers. We will go through all possible combinations and keep track of the largest sum we encounter. It's like exhaustively comparing all options to find the best one.

Here's how the algorithm would work step-by-step:

Take the first number in the collection.
Pair this first number with every other number in the collection, one at a time.
Calculate the sum of each of these pairs.
Keep track of the largest sum that you find.
Now, take the second number in the collection.
Pair this second number with every other number (except itself and the first number which was checked already) in the collection, one at a time.
Calculate the sum of each of these new pairs.
If any of these sums are larger than the largest sum you've found so far, update your record of the largest sum.
Continue this process with each number in the collection, pairing it with all the numbers that come after it.
Once you've gone through all possible pairs, the largest sum you've kept track of is the answer.

Code Implementation

def max_pair_sum_brute_force(number_list):
    maximum_sum = float('-inf')

    # Iterate through each number in the list
    for first_index in range(len(number_list)):

        # For each number, iterate through the remaining numbers to form pairs
        for second_index in range(first_index + 1, len(number_list)):

            # Calculate the sum of the current pair
            current_sum = number_list[first_index] + number_list[second_index]

            # Update maximum_sum if current_sum is greater
            if current_sum > maximum_sum:
                maximum_sum = current_sum

    # Return the maximum sum found
    return maximum_sum

Big(O) Analysis

Time Complexity

O(n²) – The provided algorithm iterates through each element of the array, and for each element, it compares it with every other element that comes after it in the array. For an array of size n, the outer loop implicitly runs for each of the n elements, and the inner part of the described logic checks roughly n/2 elements on average (as we only check elements *after* the current element). Therefore, the total number of pair checking operations approximates n * n/2. Thus, the time complexity is O(n²).

Space Complexity

O(1) – The provided plain English explanation describes a brute-force approach that iterates through pairs of numbers in the input array. It only uses a variable to store the largest sum found so far. No additional data structures, such as auxiliary arrays or hash maps, are created. Therefore, the space required beyond the input array is constant and independent of the input size N, where N is the number of elements in the array.

Optimal Solution

Approach

The best way to find the largest sum of a pair involves focusing on the biggest values first. Instead of comparing every pair, we can use a system to quickly identify and use the maximum numbers available. This avoids unnecessary calculations and speeds up the process.

Here's how the algorithm would work step-by-step:

First, find the two biggest numbers in the whole group.
If those two numbers are different, simply add them together to get the largest possible sum.
If the two biggest numbers are the same, look for the next biggest number in the group.
Add the repeated biggest number and the next biggest number together. This will guarantee that this sum is the largest.
This strategy ensures you've looked at the most important values without having to check every single combination.

Code Implementation

def find_max_pair_sum(numbers):
    first_largest_number = float('-inf')
    second_largest_number = float('-inf')

    for number in numbers:
        if number > first_largest_number:
            second_largest_number = first_largest_number
            first_largest_number = number
        elif number > second_largest_number:
            second_largest_number = number

    # If the two largest numbers are different, return their sum.
    if first_largest_number != second_largest_number:
        return first_largest_number + second_largest_number

    # Find the third largest number if the top two are the same.
    third_largest_number = float('-inf')
    for number in numbers:
        if number != first_largest_number and number > third_largest_number:
            third_largest_number = number

    # If no distinct third largest number, return sum of two largest.
    if third_largest_number == float('-inf'):
        return first_largest_number + second_largest_number

    # Return the sum of the repeated largest and the next largest.
    return first_largest_number + third_largest_number

Big(O) Analysis

Time Complexity

O(n) – The algorithm first finds the two largest numbers. This requires iterating through the array once, which takes O(n) time. Then, if the two largest numbers are equal, the algorithm needs to find the next largest number, which again requires iterating through the array in O(n) time. Since these operations are performed sequentially, the total time complexity is O(n) + O(n), which simplifies to O(n).

Space Complexity

O(1) – The algorithm described requires only a few variables to store the largest and second largest numbers, and potentially an index or two. These variables consume a fixed amount of memory regardless of the input array's size (N). Therefore, the auxiliary space remains constant as the input size grows. No additional data structures like arrays, hash maps, or recursion are involved, meaning the space complexity is O(1).

Edge Cases

Case	How to Handle
Empty array or null input	Return null or an appropriate error code/exception indicating invalid input, avoiding runtime exceptions
Array with only one element	Return null or an appropriate error code/exception since a pair cannot be formed
Array with two elements	Compare the two elements and return their sum if they meet specified criteria, otherwise return null
Array with a large number of elements (performance)	Choose an algorithm with optimal time complexity, ideally O(n) or O(n log n), to handle large datasets efficiently
Array with all identical elements	Ensure the algorithm correctly identifies and processes pairs within the identical values, if valid per problem spec
Array containing negative numbers, zeros and positive numbers	Algorithm should handle all number types correctly; no special handling is needed if the algorithm is designed to accept all numbers
Integer overflow when summing large numbers	Use a data type with a larger range (e.g., long) to store the sum and prevent potential overflow errors
Duplicate pairs exist with the same max sum	Specify whether to return all possible pairs, just one, or the number of pairs; modify algorithm to collect all valid pairs if needed

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of possible values for the integers in the array? Can I expect negative numbers?
What should I return if the array has fewer than two elements?
If there are multiple pairs with the same maximum sum, can I return any one of them?
Does the array contain duplicate numbers, and if so, should I consider them as distinct elements when finding the maximum pair sum?
Can the input array be empty or null? If so, what should I return?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the first number in the collection.
Pair this first number with every other number in the collection, one at a time.
Calculate the sum of each of these pairs.
Keep track of the largest sum that you find.
Now, take the second number in the collection.
Pair this second number with every other number (except itself and the first number which was checked already) in the collection, one at a time.
Calculate the sum of each of these new pairs.
If any of these sums are larger than the largest sum you've found so far, update your record of the largest sum.
Continue this process with each number in the collection, pairing it with all the numbers that come after it.
Once you've gone through all possible pairs, the largest sum you've kept track of is the answer.

Code Implementation

def max_pair_sum_brute_force(number_list):
    maximum_sum = float('-inf')

    # Iterate through each number in the list
    for first_index in range(len(number_list)):

        # For each number, iterate through the remaining numbers to form pairs
        for second_index in range(first_index + 1, len(number_list)):

            # Calculate the sum of the current pair
            current_sum = number_list[first_index] + number_list[second_index]

            # Update maximum_sum if current_sum is greater
            if current_sum > maximum_sum:
                maximum_sum = current_sum

    # Return the maximum sum found
    return maximum_sum

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, find the two biggest numbers in the whole group.
If those two numbers are different, simply add them together to get the largest possible sum.
If the two biggest numbers are the same, look for the next biggest number in the group.
Add the repeated biggest number and the next biggest number together. This will guarantee that this sum is the largest.
This strategy ensures you've looked at the most important values without having to check every single combination.

Code Implementation

def find_max_pair_sum(numbers):
    first_largest_number = float('-inf')
    second_largest_number = float('-inf')

    for number in numbers:
        if number > first_largest_number:
            second_largest_number = first_largest_number
            first_largest_number = number
        elif number > second_largest_number:
            second_largest_number = number

    # If the two largest numbers are different, return their sum.
    if first_largest_number != second_largest_number:
        return first_largest_number + second_largest_number

    # Find the third largest number if the top two are the same.
    third_largest_number = float('-inf')
    for number in numbers:
        if number != first_largest_number and number > third_largest_number:
            third_largest_number = number

    # If no distinct third largest number, return sum of two largest.
    if third_largest_number == float('-inf'):
        return first_largest_number + second_largest_number

    # Return the sum of the repeated largest and the next largest.
    return first_largest_number + third_largest_number

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty array or null input	Return null or an appropriate error code/exception indicating invalid input, avoiding runtime exceptions
Array with only one element	Return null or an appropriate error code/exception since a pair cannot be formed
Array with two elements	Compare the two elements and return their sum if they meet specified criteria, otherwise return null
Array with a large number of elements (performance)	Choose an algorithm with optimal time complexity, ideally O(n) or O(n log n), to handle large datasets efficiently
Array with all identical elements	Ensure the algorithm correctly identifies and processes pairs within the identical values, if valid per problem spec
Array containing negative numbers, zeros and positive numbers	Algorithm should handle all number types correctly; no special handling is needed if the algorithm is designed to accept all numbers
Integer overflow when summing large numbers	Use a data type with a larger range (e.g., long) to store the sum and prevent potential overflow errors
Duplicate pairs exist with the same max sum	Specify whether to return all possible pairs, just one, or the number of pairs; modify algorithm to collect all valid pairs if needed