Sponsored
Sponsored
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 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.
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5int minPairSum(std::vector<int>& nums) {
6 std::sort(nums.begin(), nums.end());
7 int maxSum = 0;
8 for (int i = 0; i < nums.size() / 2; i++) {
9 int pairSum = nums[i] + nums[nums.size() - 1 - i];
10 maxSum = std::max(maxSum, pairSum);
11 }
12 return maxSum;
13}
14
15int main() {
16 std::vector<int> nums = {3, 5, 2, 3};
17 int result = minPairSum(nums);
18 std::cout << "Output: " << result << std::endl;
19 return 0;
20}The C++ solution sorts the vector using std::sort and then pairs elements from the beginning and end of the sorted list to minimize the maximum pair sum.
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.
The time complexity remains O(n log n) due to sorting, and the space complexity is O(1).
1
This JavaScript version pairs elements based on their index positions in the sorted list.