Sponsored
The core idea of this approach is to pair up the elements after sorting the array to maximize the minimum sum of pairs. By sorting the array, the smallest values are naturally grouped together, maximizing your result. After sorting, pair the elements from the start with their consecutive neighbor. This guarantees maximal sum of mins in pairs.
Let us see how we can implement this in various programming languages:
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as no additional space is used except for input.
1using System;
2
3class Program
4{
5 static int ArrayPairSum(int[] nums)
6 {
7 Array.Sort(nums);
8 int sum = 0;
9 for (int i = 0; i < nums.Length; i += 2)
10 {
11 sum += nums[i];
12 }
13 return sum;
14 }
15
16 static void Main()
17 {
18 int[] nums = {6, 2, 6, 5, 1, 2};
19 int result = ArrayPairSum(nums);
20 Console.WriteLine(result);
21 }
22}This C# solution sorts the array using Array.Sort(). By iterating through the array and picking up elements at even index positions, it calculates the required sum.
Instead of using a traditional sorting method, we can optimize the sorting step with a counting sort. This is particularly useful given the constraints - limited range of numbers. This approach uses a counting array to sort, followed by picking elements at alternate indices in a manner similar to the previous approach.
Time Complexity: O(n + range) due to counting sort.
Space Complexity: O(range) for the count array.
1#include <vector>
#include <cstring>
int arrayPairSum(std::vector<int>& nums) {
const int RANGE = 20001;
int count[RANGE];
std::memset(count, 0, sizeof(count));
for (int num : nums) {
++count[num + 10000];
}
int sum = 0;
bool odd = false;
for (int i = 0; i < RANGE; ++i) {
while (count[i] > 0) {
if (!odd) {
sum += (i - 10000);
}
odd = !odd;
--count[i];
}
}
return sum;
}
int main() {
std::vector<int> nums = {6, 2, 6, 5, 1, 2};
int result = arrayPairSum(nums);
std::cout << result << std::endl;
return 0;
}The C++ code implemented counting sort logic by tracking each number's count and using this information to reconstruct the nums sequence for optimal pairing and summation.