Largest Pair Sum

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Find the largest sum of any two elements in the array. Linear scan for max and second max.

Algorithm

1Single pass: track max1 and max2. Answer = max1 + max2.

Common Pitfalls

•O(n) linear scan. If array can have negatives, simply sort and take last two elements.

Largest Pair Sum.java

Java

// Approach: Linear scan for the two largest distinct values.
// Time: O(n) Space: O(1)
class Solution {
    public static int pairsum(int[] arr) {
        int first = Math.max(arr[0], arr[1]);
        int second = Math.min(arr[0], arr[1]);
        for (int i = 2; i < arr.length; i++) {
            if (arr[i] >= first) {
                second = first;
                first = arr[i];
            } else if (arr[i] > second) {
                second = arr[i];
            }
        }
        return first + second;
    }
}

Was this solution helpful?