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 <stdio.h>
2#include <stdlib.h>
3
4int cmpfunc (const void * a, const void * b) {
5 return ( *(int*)a - *(int*)b );
6}
7
8int minPairSum(int* nums, int numsSize) {
9 qsort(nums, numsSize, sizeof(int), cmpfunc);
10 int maxSum = 0;
11 for (int i = 0; i < numsSize / 2; i++) {
12 int pairSum = nums[i] + nums[numsSize - 1 - i];
13 if (pairSum > maxSum) {
14 maxSum = pairSum;
15 }
16 }
17 return maxSum;
18}
19
20int main() {
21 int nums[] = {3, 5, 2, 3};
22 int result = minPairSum(nums, 4);
23 printf("Output: %d\n", result);
24 return 0;
25}The solution sorts the array using the C standard library function qsort(). It then iteratively forms pairs of elements from the two ends (smallest and largest), computes the pair sum, and tracks the maximum pair sum encountered.
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.