1877. Minimize Maximum Pair Sum in Array

Time: O(n log n)

Space: O(1)

Intuition

Pair elements to maximize minimum pair sum. Sort and pair first with last, second with second-last. This maximizes the minimum.

Algorithm

1Sort array. For each i: pair nums[i] with nums[n-1-i]. Max of these sums is the answer.

Common Pitfalls

•Sort + pair opposite ends. Optimal pairing minimizes the maximum of minimum pairs.

1877.cs

// Approach: Sort array; pair smallest with largest; maximum pair sum is minimized.
// Time: O(n log n) Space: O(1)

public class Solution
{
    public int MinPairSum(int[] nums)
    {
        int ans = 0;

        Array.Sort(nums);

        int i = 0, j = nums.Length - 1;
        while (i < j)
            ans = Math.Max(ans, nums[i++] + nums[j--]);

        return ans;
    }
}

Was this solution helpful?