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

Solution

Method 1 – Two Pointers After Sorting

Intuition

To minimize the maximum pair sum, pair the smallest element with the largest, the second smallest with the second largest, and so on. This balances the sums and ensures the largest pair sum is as small as possible.

Approach

Sort the array in ascending order.
Use two pointers: one at the start, one at the end.
Pair elements at the start and end, moving inward.
For each pair, compute the sum and track the maximum.
Return the minimum possible maximum pair sum.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int minPairSum(vector<int>& nums) {\n        sort(nums.begin(), nums.end());\n        int ans = 0, n = nums.size();\n        for (int i = 0; i < n / 2; ++i) {\n            ans = max(ans, nums[i] + nums[n - 1 - i]);\n        }\n        return ans;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    int</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> minPairSum</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">></span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x26;</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> nums</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">) {</span></span>\n<span class=\"line\"><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">        sort</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(nums.</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">begin</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(), nums.</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">end</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">());</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F9

Related Tags