Largest Pair Sum

Find the largest pair sum in an array of distinct integers.

Examples :

Input: arr[] = [12, 34, 10, 6, 40]
Output: 74
Explanation: Sum of 34 and 40 is the largest, i.e, 34 + 40 = 74.

Input: arr[] = [10, 20, 30]
Output: 50
Explanation: 20 + 30 = 50.

Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)

Constraints:
2 ≤ arr.size() ≤ 10⁶
0 ≤ arr[i] ≤ 10⁶

Approach 01:

#include <vector>
#include <climits>
using namespace std;

class Solution {
public:
    int pairsum(vector<int>& numbers) {
        int largestNumber = INT_MIN;
        int secondLargestNumber = INT_MIN;

        // Find the largest number in the array
        for (int currentNumber : numbers) {
            if (currentNumber > largestNumber)
                largestNumber = currentNumber;
        }

        // Find the second largest number in the array
        for (int currentNumber : numbers) {
            if (currentNumber == largestNumber)
                continue;
            else if (currentNumber > secondLargestNumber)
                secondLargestNumber = currentNumber;
        }

        return largestNumber + secondLargestNumber;
    }
};

class Solution:
    def pairsum(self, numbers):
        largestNumber = float('-inf')
        secondLargestNumber = float('-inf')

        # Find the largest number in the list
        for currentNumber in numbers:
            if currentNumber > largestNumber:
                largestNumber = currentNumber

        # Find the second largest number in the list
        for currentNumber in numbers:
            if currentNumber == largestNumber:
                continue
            elif currentNumber > secondLargestNumber:
                secondLargestNumber = currentNumber

        return largestNumber + secondLargestNumber

Time Complexity

• Finding the largest number:

  The function iterates through the array once to find the largest number. This step takes \(O(n)\), where \(n\) is the size of the input vector numbers.

• Finding the second largest number:

  After finding the largest number, the function iterates through the array again to find the second largest number. This step also takes \(O(n)\).

• Overall Time Complexity:

  The overall time complexity is \(O(n)\), where \(n\) is the size of the input vector, as the function performs two separate passes over the array.

Space Complexity

• Auxiliary Space:

  The function uses a constant amount of extra space to store the two largest numbers (largestNumber and secondLargestNumber). Thus, the auxiliary space complexity is \(O(1)\).

• Overall Space Complexity:

  The overall space complexity is \(O(1)\), since the amount of extra space used does not depend on the size of the input vector.