Minimize Maximum Pair Sum in Array

Medium
1472.

Minimize Maximum Pair Sum in Array

Minimize Maximum Pair Sum in Array is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.

You are given an array nums of even length n. Split its elements into n / 2 pairs so that every element is in exactly one pair. The pair sum of (a, b) is a + b.

Return the smallest possible value of the largest pair sum.

Example 1

Input
nums = [1,9,4,6]
Output
10
Explanation
Pairs `(1,9)` and `(4,6)` both sum to 10.

Example 2

Input
nums = [2,8,3,5,1,9]
Output
10
Explanation
Pairs `(1,9)`, `(2,8)` and `(3,5)`.

Example 3

Input
nums = [7,7]
Output
14

Constraints

  • n == nums.length
  • 2 <= n <= 10^5
  • n is even
  • 1 <= nums[i] <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var minPairSum = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimize Maximum Pair Sum in Array — Problem & Solution

Minimize Maximum Pair Sum in Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Minimize Maximum Pair Sum in Array is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Sorting, Greedy, Two Pointers
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given an array nums of even length n. Split its elements into n / 2 pairs so that every element is in exactly one pair. The pair sum of (a, b) is a + b.

Return the smallest possible value of the largest pair sum.

Example 1

Input: nums = [1,9,4,6]
Output: 10
Explanation: Pairs `(1,9)` and `(4,6)` both sum to 10.

Example 2

Input: nums = [2,8,3,5,1,9]
Output: 10
Explanation: Pairs `(1,9)`, `(2,8)` and `(3,5)`.

Example 3

Input: nums = [7,7]
Output: 14

Constraints

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

Hints for Minimize Maximum Pair Sum in Array

  1. Hint 1

    The largest element has to be paired with something. Which partner keeps its pair sum smallest?

  2. Hint 2

    Pair the largest with the smallest, then the second largest with the second smallest, and so on.

  3. Hint 3

    Sort the array and take the maximum of nums[i] + nums[n - 1 - i].

How to solve Minimize Maximum Pair Sum in Array

Sort the array and pair the smallest with the largest, the second smallest with the second largest, and so on. The answer is the largest of these sums.

Approach

  1. Sort nums ascending.
  2. For i from 0 to n/2 - 1, compute nums[i] + nums[n - 1 - i].
  3. Return the maximum of these sums.

Why it works

Exchange argument: if the largest element M is paired with x while the smallest m is paired with y, swapping partners to (M, m) and (x, y) gives sums M + m <= M + x and x + y <= M + x, so the maximum does not grow. Repeating on the remaining elements yields the sorted pairing.

Complexity

  • Time — O(n log n)
  • Space — O(1) beyond the sort

Pitfalls

  • Pairing neighbours after sorting (nums[0] with nums[1], …) maximises the largest sum instead of minimising it.
  • Only half the indices need to be visited — each pair is counted once.
  • Pair sums reach at most 2 · 10^5, so there is no overflow.

Reference solution

Python

from typing import List

def minPairSum(nums: List[int]) -> int:
    a = sorted(nums)
    n = len(a)
    return max(a[i] + a[n - 1 - i] for i in range(n // 2))

Java

public static int minPairSum(int[] nums) {
    int[] a = nums.clone();
    Arrays.sort(a);
    int n = a.length, best = 0;
    for (int i = 0; i < n / 2; i++) best = Math.max(best, a[i] + a[n - 1 - i]);
    return best;
}

C++

int minPairSum(vector<int>& nums) {
    vector<int> a(nums);
    sort(a.begin(), a.end());
    int n = a.size(), best = 0;
    for (int i = 0; i < n / 2; i++) best = max(best, a[i] + a[n - 1 - i]);
    return best;
}

JavaScript

var minPairSum = function(nums) {
    var a = nums.slice().sort(function(x, y) { return x - y; });
    var n = a.length, best = 0;
    for (var i = 0; i < n / 2; i++) best = Math.max(best, a[i] + a[n - 1 - i]);
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms