Minimize Maximum Pair Sum in Array solution and explanation
IBM
Google
9 more videos on this problem
Minimize Maximum Pair Sum in Array | Intuition | Similar Problems | Leetcode 1877 | codestorywithMIKcodestorywithMIK · 11:28 · 16K views
Leetcode Solution - 1877 Minimize Maximum Pair Sum in ArrayJohn Leonardo · 3:55 · 1K views
Minimize Maximum Pair Sum in Array | LeetCode 1877 🔥 Binary Search to Two Pointer Study Placement · 11:45 · 726 views
1877. Minimize Maximum Pair Sum in Array | Leetcode Daily - PythonLeetcode Daily · 8:53 · 664 views
Solving LeetCode 1877 Minimize Maximum Pair Sum in Array | Easy | Two Pointers | AmazonCode Harmony · 4:48 · 619 views
Leetcode 1877 Minimize Maximum Pair Sum in ArrayThinkCode · 3:45 · 307 views
Minimize Maximum Pair Sum in Array | LeetCode 1877 | Sorting | Java Code | Developer CoderDeveloper Coder · 7:20 · 241 views
Minimize Maximum Pair Sum in Array | LeetCode 1877 | Sorting | 2 PointerscodeTips · 11:45 · 232 views
Minimize Maximum Pair Sum in Array | LeetCode 1877 | JAVA | LeetCode in TAMIL !AlgoTube · 8:45 · 204 views
Minimize Maximum Pair Sum in Array | LeetCode 1877 - Pythonimpoldev · 5:25 · 184 views
The problem
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 bemax(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
numsis 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.length2 <= n <= 105nis 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.
def minPairSum(nums):
nums.sort()
max_sum = 0
for i in range(len(nums) // 2):
pair_sum = nums[i] + nums[-1-i]
if pair_sum > max_sum:
max_sum = pair_sum
return max_sum
# Testing the function
test_nums = [3, 5, 2, 3]
print('Output:', minPairSum(test_nums)) # Output: 7import java.util.Arrays;
public class Solution {
public int minPairSum(int[] nums) {
Arrays.sort(nums);
int maxSum = 0;
for (int i = 0; i < nums.length / 2; i++) {
int pairSum = nums[i] + nums[nums.length - 1 - i];
maxSum = Math.max(maxSum, pairSum);
}
return maxSum;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {3, 5, 2, 3};
System.out.println("Output: " + sol.minPairSum(nums)); // Output should be 7
}
}#include <iostream>
#include <vector>
#include <algorithm>
int minPairSum(std::vector<int>& nums) {
std::sort(nums.begin(), nums.end());
int maxSum = 0;
for (int i = 0; i < nums.size() / 2; i++) {
int pairSum = nums[i] + nums[nums.size() - 1 - i];
maxSum = std::max(maxSum, pairSum);
}
return maxSum;
}
int main() {
std::vector<int> nums = {3, 5, 2, 3};
int result = minPairSum(nums);
std::cout << "Output: " << result << std::endl;
return 0;
}function minPairSum(nums) {
nums.sort((a, b) => a - b);
let maxSum = 0;
for (let i = 0; i < nums.length / 2; i++) {
const pairSum = nums[i] + nums[nums.length - 1 - i];
if (pairSum > maxSum) {
maxSum = pairSum;
}
}
return maxSum;
}
// Test
evenArray = [3, 5, 2, 3];
console.log('Output:', minPairSum(evenArray)); // Output: 7#include <stdio.h>
#include <stdlib.h>
int cmpfunc (const void * a, const void * b) {
return ( *(int*)a - *(int*)b );
}
int minPairSum(int* nums, int numsSize) {
qsort(nums, numsSize, sizeof(int), cmpfunc);
int maxSum = 0;
for (int i = 0; i < numsSize / 2; i++) {
int pairSum = nums[i] + nums[numsSize - 1 - i];
if (pairSum > maxSum) {
maxSum = pairSum;
}
}
return maxSum;
}
int main() {
int nums[] = {3, 5, 2, 3};
int result = minPairSum(nums, 4);
printf("Output: %d\n", result);
return 0;
}using System;
public class Solution {
public int MinPairSum(int[] nums) {
Array.Sort(nums);
int maxSum = 0;
for (int i = 0; i < nums.Length / 2; i++) {
int pairSum = nums[i] + nums[nums.Length - 1 - i];
if (pairSum > maxSum) {
maxSum = pairSum;
}
}
return maxSum;
}
public static void Main() {
Solution sol = new Solution();
int[] nums = {3, 5, 2, 3};
Console.WriteLine("Output: " + sol.MinPairSum(nums)); // Output should be 7
}
}The Python solution leverages the built-in sort() method to sort the list, then uses a loop to calculate the pair sums and determine the maximum.
Time complexity is O(n log n) due to sorting, and space complexity is O(1) if ignoring the input length (as sorting is in-place).
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.
def minPairSum(nums):
nums.sort()
max_sum = 0
for i in range(len(nums) // 2):
pair_sum = nums[i] + nums[-1-i]
if pair_sum > max_sum:
max_sum = pair_sum
return max_sum
# Testing the function
test_nums = [3, 5, 2, 3]
print('Output:', minPairSum(test_nums))import java.util.Arrays;
public class Solution {
public int minPairSum(int[] nums) {
Arrays.sort(nums);
int maxSum = 0, pairSum;
for (int i = 0; i < nums.length / 2; ++i) {
pairSum = nums[i] + nums[nums.length - 1 - i];
if (pairSum > maxSum)
maxSum = pairSum;
}
return maxSum;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {3, 5, 2, 3};
System.out.println("Output: " + sol.minPairSum(nums));
}
}#include <iostream>
#include <vector>
#include <algorithm>
int minPairSum(std::vector<int>& nums) {
std::sort(nums.begin(), nums.end());
int maxSum = 0, pairSum;
for (size_t i = 0; i < nums.size() / 2; ++i) {
pairSum = nums[i] + nums[nums.size() - 1 - i];
maxSum = std::max(maxSum, pairSum);
}
return maxSum;
}
int main() {
std::vector<int> nums = {3, 5, 2, 3};
int result = minPairSum(nums);
std::cout << "Output: " << result << std::endl;
return 0;
}function minPairSum(nums) {
nums.sort((a, b) => a - b);
let maxSum = 0;
for (let i = 0; i < nums.length / 2; ++i) {
const pairSum = nums[i] + nums[nums.length - 1 - i];
if (pairSum > maxSum) maxSum = pairSum;
}
return maxSum;
}
// Test example
console.log('Output:', minPairSum([3, 5, 2, 3])); // Output 7#include <stdio.h>
#include <stdlib.h>
int cmpfunc (const void * a, const void * b) {
return ( *(int*)a - *(int*)b );
}
int minPairSum(int* nums, int numsSize) {
qsort(nums, numsSize, sizeof(int), cmpfunc);
int maxSum = 0, pairSum;
for (int i = 0; i < numsSize / 2; ++i) {
pairSum = nums[i] + nums[numsSize - 1 - i];
if (pairSum > maxSum) {
maxSum = pairSum;
}
}
return maxSum;
}
int main() {
int nums[] = {3, 5, 2, 3};
int result = minPairSum(nums, 4);
printf("Output: %d\n", result);
return 0;
}using System;
public class Solution {
public int MinPairSum(int[] nums) {
Array.Sort(nums);
int maxSum = 0, pairSum;
for (int i = 0; i < nums.Length / 2; ++i) {
pairSum = nums[i] + nums[nums.Length - 1 - i];
if (pairSum > maxSum)
maxSum = pairSum;
}
return maxSum;
}
public static void Main() {
Solution sol = new Solution();
int[] nums = {3, 5, 2, 3};
Console.WriteLine("Output: " + sol.MinPairSum(nums));
}
}The Python implementation uses index-based pairing on a sorted list to determine the minimal maximum pair sum.
The approach has a time complexity of O(n log n) and a space complexity of O(1).
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.
function minPairSum(nums: number[]): number {
nums.sort((a, b) => a - b);
let ans = 0;
const n = nums.length;
for (let i = 0; i < n >> 1; ++i) {
ans = Math.max(ans, nums[i] + nums[n - 1 - i]);
}
return ans;
}func minPairSum(nums []int) (ans int) {
sort.Ints(nums)
n := len(nums)
for i, x := range nums[:n>>1] {
ans = max(ans, x+nums[n-1-i])
}
return
}impl Solution {
pub fn min_pair_sum(nums: Vec<i32>) -> i32 {
let mut nums = nums;
nums.sort();
let mut ans = 0;
let n = nums.len();
for i in 0..n / 2 {
ans = ans.max(nums[i] + nums[n - i - 1]);
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sorting and Two-Pointer Approach | Time complexity is O(n log n) due to sorting, and space complexity is O(1) if ignoring the input length (as sorting is in-place). |
| Direct Index Pairing Strategy | The approach has a time complexity of O(n log n) and a space complexity of O(1). |
| Greedy | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Enumeration | O((n-1)!!) | O(n) | Conceptual understanding or very small input sizes |
| Sorting + Two-Pointer Greedy | O(n log n) | O(1) | Standard optimal approach for unsorted arrays |
| Direct Index Pairing After Sort | O(n log n) | O(1) | Cleaner implementation once the array is sorted |
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.