LeetCode - Minimize Maximum Pair Sum in Array

Problem statement

The pair sum of a pair (a, b) is equal to a + b. The maximum pair sum is the largest pair sum in a list of pairs.

For example, if we have pairs (1, 5), (2, 3), and (4, 4), the maximum pair sum would be max(1 + 5, 2 + 3, 4 + 4) = max(6, 5, 8) = 8.

Given an array nums of even length n, pair up the elements of nums into n / 2 pairs such that:

Each element of nums is in exactly one pair, and
The maximum pair sum is minimized.

Return the minimized **maximum pair sum* after optimally pairing up the elements*.

Problem statement taken from: https://leetcode.com/problems/minimize-maximum-pair-sum-in-array

Example 1:

Input: nums = [3, 5, 2, 3]
Output: 7
Explanation: The elements can be paired up into pairs (3, 3) and (5, 2).
The maximum pair sum is max(3 + 3, 5 + 2) = max(6, 7) = 7.

Example 2:

Input: nums = [3, 5, 4, 2, 4, 6]
Output: 8
Explanation: The elements can be paired up into pairs (3, 5), (4, 4), and (6, 2).
The maximum pair sum is max(3 + 5, 4 + 4, 6 + 2) = max(8, 8, 8) = 8.

Constraints:

- n == nums.length
- 2 <= n <= 10^5
- n is even
- 1 <= nums[i] <= 10^5

Explanation

Sorting

We sort the array first and then iterate over the loop to form pairs (i, j). i will start from index 0, and j will begin from the last index.

We increment and decrement i and j, respectively, to form the next pairs till i < j.

Let's check the algorithm first.

- sort(nums.begin(), nums.end())
  maxSum = 0
  i = 0
  j = nums.size() - 1

- loop while i < j
  - if nums[i] + nums[j] > maxSum
    - maxSum = nums[i] + nums[j]

  - i++
    j--
- while end

- return maxSum

The time complexity of the above approach is O(n * log(n)), and the space complexity is O(1).

Let's check our algorithm in C++, Golang, and JavaScript.

C++ solution

class Solution {
public:
    int minPairSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int maxSum = 0, i = 0, j = nums.size() - 1;

        while(i < j) {
            if(nums[i] + nums[j] > maxSum) {
                maxSum = nums[i] + nums[j];
            }

            i++;
            j--;
        }

        return maxSum;
    }
};

Golang solution

func minPairSum(nums []int) int {
    sort.Ints(nums)
    i, j := 0, len(nums) - 1
    maxSum := 0

    for i < j {
        if nums[i] + nums[j] > maxSum {
            maxSum = nums[i] + nums[j]
        }

        i++
        j--
    }

    return maxSum
}

JavaScript solution

var minPairSum = function(nums) {
    nums.sort((a, b) => a - b);
    let i = 0, j = nums.length - 1;
    let maxSum = 0;

    while(i < j) {
        maxSum = Math.max(nums[i] + nums[j], maxSum);

        i++;
        j--;
    }

    return maxSum;
};

Let's dry-run our algorithm to see how the solution works.

Input: nums = [3, 5, 5, 2, 4, 6]

Step 1: sort(nums.begin(), nums.end())
        nums = [2, 3, 4, 5, 5, 6]

        maxSum = 0
        i = 0
        j = nums.size() - 1
          = 6 - 1
          = 5

Step 2: loop while i < j
          0 < 5
          true

          if nums[i] + nums[j] > maxSum
             nums[0] + nums[5] > 0
             2 + 6 > 0
             8 > 0
             true

             maxSum = nums[i] + nums[j]
                    = nums[0] + nums[5]
                    = 2 + 6
                    = 8

          i++
          i = 1

          j--
          j = 4

Step 3: loop while i < j
          1 < 4
          true

          if nums[i] + nums[j] > maxSum
             nums[1] + nums[4] > 8
             3 + 5 > 8
             8 > 8
             false

          i++
          i = 2

          j--
          j = 3

Step 4: loop while i < j
          2 < 3
          true

          if nums[i] + nums[j] > maxSum
             nums[2] + nums[3] > 8
             4 + 5 > 8
             9 > 8
             true

             maxSum = nums[i] + nums[j]
                    = nums[2] + nums[3]
                    = 4 + 5
                    = 9

          i++
          i = 3

          j--
          j = 2

Step 5: loop while i < j
          3 < 2
          false

Step 6: return maxSum

We return the answer as 9.

Blog