algoadvance

Given a 0-indexed integer array nums, the sum of two elements nums[i] and nums[j] (where i != j) is called a pair sum. Suppose the maximum pair sum in an array is the largest such sum.

Return the maximum pair sum that can be formed in the array.

Example

Example 1:

Input: nums = [5,6,2,7,4]
Output: 13
Explanation: The pair (6, 7) forms the maximum pair sum 13.

Example 2:

Input: nums = [1,2,3,4]
Output: 7
Explanation: The pair (3, 4) forms the maximum pair sum 7.

Clarifying Questions

1. Can the array contain negative numbers?
   • Usually, the array can contain negative numbers, but it would be useful to confirm.
2. What is the minimum and maximum length of the input array nums?
   • Confirming boundary conditions such as an array of length 1 would be important.
3. Are there any constraints around space and time complexity?

Strategy

To solve this problem, we need to identify the two largest numbers in the array, as their sum would be the maximum pair sum.

Steps:

1. Sort the array.
2. The two largest numbers will be the last two elements of the sorted array.
3. Sum these two largest numbers and return the result.

Sorting Approach:

1. Sort the array in ascending order.
2. Identify the two largest numbers: these would be the last two elements in the sorted list.
3. Compute their sum and return it.

Time Complexity Analysis:

• Sorting the array will take (O(n \log n)).
• Accessing the last two elements and computing their sum is (O(1)).
• Thus, the overall time complexity is dominated by the sorting step, which is (O(n \log n)).

Code

def max_pair_sum(nums):
    # Sort the array
    nums.sort()
    # The maximum pair sum is the sum of the last two elements
    return nums[-1] + nums[-2]

# Test Cases
print(max_pair_sum([5, 6, 2, 7, 4]))  # Output: 13
print(max_pair_sum([1, 2, 3, 4]))  # Output: 7

This code will effectively provide the maximum pair sum by first sorting the array and then summing the two largest elements.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?