Skip to main content
Talentd

Minimize Maximum Pair Sum in Array - Solution & Explanation

MediumArrayTwo PointersGreedySorting17 min readAsked at: Amazon, Meta, IBM +3
Practice this problem

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.

 

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 <= 105
  • n is even.
  • 1 <= nums[i] <= 105

Approach Overview

Problem Overview: You are given an even-length array of integers. Pair up the elements so every number belongs to exactly one pair. Among all pairs, compute the maximum pair sum and minimize that value. The goal is to choose pairings that keep the largest pair sum as small as possible.

Approach 1: Brute Force Pairing (Exponential Time)

The brute force idea is to try every possible way to form pairs, compute the maximum pair sum for each configuration, and return the minimum among them. This requires generating all pair combinations and tracking the worst pair sum per configuration. The number of pairings grows extremely fast, making the time complexity roughly O((n-1)!!) (factorial-like growth) with O(n) auxiliary space for recursion or bookkeeping. This approach mainly helps you reason about the objective: minimizing the largest pair sum across all pairings.

Approach 2: Sorting and Two-Pointer Greedy (O(n log n) time, O(1) space)

The key observation: the maximum pair sum is minimized when the smallest element is paired with the largest element. After sorting the array, use two pointers—one at the beginning and one at the end. Pair nums[left] with nums[right], compute their sum, and track the maximum across all such pairs. Move both pointers inward until they meet. Sorting ensures large numbers are balanced by small numbers, preventing a large value from being paired with another large value. This greedy pairing strategy produces the optimal answer.

This approach relies on sorting to structure the numbers and then applies a classic two pointers sweep from both ends. The greedy decision—always pairing extremes—keeps the worst-case pair sum as small as possible. Time complexity is dominated by sorting at O(n log n), while the pointer scan runs in O(n) time with O(1) extra space.

Approach 3: Direct Index Pairing After Sort (O(n log n) time, O(1) space)

This is a simplified variation once the array is sorted. Instead of explicitly maintaining two pointers, iterate through the first half of the array and pair index i with n - 1 - i. Each iteration calculates nums[i] + nums[n-1-i] and updates the maximum pair sum seen so far. The logic is identical to the two-pointer method but uses direct index symmetry. The algorithm still depends on sorting (O(n log n)) and scans only half the array (O(n)), using constant extra space.

Recommended for interviews: The expected solution is the greedy strategy using sorting plus two pointers. Interviewers want to see that you recognize the pairing pattern: smallest with largest minimizes the worst-case sum. Mentioning the brute force approach shows problem understanding, but implementing the greedy greedy solution demonstrates algorithmic insight and leads directly to the optimal O(n log n) implementation.

Approach 1: Sorting and Two-Pointer Approach

Sort the array first. Then, use a two-pointer technique to pick the smallest and largest elements to form pairs. Start with the smallest, pair it with the largest, and move inwards. This minimizes the largest sum in each pair.

The solution sorts the array using the C standard library function qsort(). It then iteratively forms pairs of elements from the two ends (smallest and largest), computes the pair sum, and tracks the maximum pair sum encountered.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

The time complexity is O(n log n) due to the sorting step, and the space complexity is O(1) as we don't use any additional data structures.

Try this approach in the editor →

Approach 2: Direct Index Pairing Strategy

Use the sorted array but pair elements directly based on their index positions in a staggered manner. This approach takes advantage of the sorted order to pair elements directly based on their index positions.

This solution leverages the sorted nature of the list to directly pair numbers in the staggered pattern (index-based).

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

The time complexity remains O(n log n) due to sorting, and the space complexity is O(1).

Try this approach in the editor →

Approach 3: Greedy

To minimize the maximum pair sum in the array, we can pair the smallest number with the largest number, the second smallest with the second largest, and so on.

Therefore, we can first sort the array, then use two pointers to point to the two ends of the array. Calculate the sum of the numbers pointed to by the two pointers, update the maximum pair sum, then move the left pointer one step to the right and the right pointer one step to the left. Continue this process until the two pointers meet, and we will get the minimum maximum pair sum.

The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the length of the array nums.

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sorting and Two-Pointer Approach

The time complexity is O(n log n) due to the sorting step, and the space complexity is O(1) as we don't use any additional data structures.

Direct Index Pairing Strategy

The time complexity remains O(n log n) due to sorting, and the space complexity is O(1).

Greedy—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Pair EnumerationO((n-1)!!)O(n)Conceptual understanding or very small input sizes
Sorting + Two-Pointer GreedyO(n log n)O(1)Standard optimal approach for unsorted arrays
Direct Index Pairing After SortO(n log n)O(1)Cleaner implementation once the array is sorted

Video Solution

Minimize Maximum Pair Sum in Array | Intuition | Similar Problems | Leetcode 1877 | codestorywithMIK • codestorywithMIK • 16,129 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimize Maximum Pair Sum in Array easy or hard?
The problem is classified as Medium on LeetCode. The implementation is straightforward once you recognize the greedy insight: pair the smallest and largest elements after sorting. The challenge lies in identifying why that pairing minimizes the maximum pair sum.
Minimize Maximum Pair Sum in Array Python/Java solution
In Python or Java, first sort the array using the built-in sort function. Then use two indices—one starting at the beginning and the other at the end—to compute pair sums while tracking the maximum. Continue until the pointers cross, returning the maximum pair sum encountered.
How to solve Minimize Maximum Pair Sum in Array in O(n)?
A pure O(n) solution is generally not feasible without additional constraints because the algorithm relies on ordering the elements. Sorting the array (O(n log n)) allows you to pair the smallest and largest elements greedily. After sorting, computing pair sums with two pointers takes O(n).
What is the best approach for Minimize Maximum Pair Sum in Array?
The optimal approach sorts the array and pairs the smallest element with the largest using a two-pointer technique. This greedy strategy ensures large values are balanced with small ones, minimizing the worst pair sum. The time complexity is O(n log n) due to sorting, with O(1) additional space.
Is Minimize Maximum Pair Sum in Array asked at Google/Amazon/Meta?
Greedy pairing and two-pointer problems similar to this one frequently appear in interviews at companies like Amazon, Google, and Meta. The problem tests whether you recognize patterns after sorting and apply a greedy strategy to minimize a maximum value.
What data structure is used in Minimize Maximum Pair Sum in Array?
The solution primarily uses arrays along with sorting and the two-pointer technique. No complex data structures are required. The algorithm simply rearranges the array order and evaluates pair sums from both ends.
What is the time complexity of Minimize Maximum Pair Sum in Array?
The optimal solution runs in O(n log n) time because the array must be sorted before pairing elements. After sorting, a single linear scan with two pointers computes the maximum pair sum in O(n) time. The overall space complexity is O(1) if sorting is done in-place.

Ready to solve this problem?

Practice Minimize Maximum Pair Sum in Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays