Minimize Maximum Pair Sum in Array - Practice Coding Problems

Minimize Maximum Pair Sum in Array - 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 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.

Input & Output

Example 1 — Basic Case

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

› Output: 7

💡 Note: After sorting [2,3,4,5], pair (2,5) and (3,4). Maximum pair sum is max(7,7) = 7

Example 2 — Larger Array

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

› Output: 8

💡 Note: After sorting [2,3,4,4,5,6], pair (2,6), (3,5), (4,4). Maximum pair sum is max(8,8,8) = 8

Example 3 — Minimum Size

$ Input: nums = [1,4]

› Output: 5

💡 Note: Only one pair possible: (1,4) with sum 5

Constraints

2 ≤ nums.length ≤ 10⁵
nums.length is even
1 ≤ nums[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array of even length that needs pairing

Sort & Pair

Sort array and pair smallest with largest

Find Maximum

Return the maximum sum among all pairs

Key Takeaway

🎯 Key Insight: Pairing smallest with largest elements minimizes the maximum pair sum

Asked in

G Google 12 f Facebook 8 a Amazon 6

The key insight is that pairing the smallest element with the largest element minimizes the maximum pair sum. Best approach is the greedy algorithm: sort the array and pair elements from both ends. Time: O(n log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Pairings	O(n!)	O(n)	Generate all possible ways to pair elements and find the one with minimum maximum pair sum
Greedy - Sort and Pair Optimally	O(n log n)	O(1)	Sort the array and pair smallest with largest elements to minimize maximum pair sum

Brute Force - Try All Pairings — Algorithm Steps

Generate all possible ways to pair n elements
For each pairing, calculate all pair sums
Find maximum sum in each pairing
Return the minimum of all maximum sums

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate All Pairings

Create every possible way to pair elements

Calculate Max Sum

Find maximum pair sum in each pairing

Find Minimum

Return smallest maximum sum found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int minMaxSum = INT_MAX;

void generatePairings(int* available, int availableSize, int pairs[][2], int pairCount) {
    if (availableSize == 0) {
        int maxSum = 0;
        for (int i = 0; i < pairCount; i++) {
            int sum = pairs[i][0] + pairs[i][1];
            if (sum > maxSum) maxSum = sum;
        }
        if (maxSum < minMaxSum) minMaxSum = maxSum;
        return;
    }
    
    int first = available[0];
    for (int i = 1; i < availableSize; i++) {
        int partner = available[i];
        
        int newAvailable[20];
        int newSize = 0;
        for (int j = 1; j < availableSize; j++) {
            if (j != i) {
                newAvailable[newSize++] = available[j];
            }
        }
        
        pairs[pairCount][0] = first;
        pairs[pairCount][1] = partner;
        generatePairings(newAvailable, newSize, pairs, pairCount + 1);
    }
}

int solution(int* nums, int numsSize) {
    minMaxSum = INT_MAX;
    int pairs[10][2];
    generatePairings(nums, numsSize, pairs, 0);
    return minMaxSum;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[20];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(nums, size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n!)

Generating all possible pairings is factorial time

⚠ Quadratic Growth

Space Complexity

O(n)

Need to store current pairing configuration

⚡ Linearithmic Space

89.2K Views

Medium Frequency

~15 min Avg. Time

1.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Pairings — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler