Largest Pair Sum

JavaView on GFG

Time: O(n)

Space: O(1)

Problem Overview

Find the largest sum of any two elements in the array.

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?