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.
1import java.util.Arrays;
2
3public class Solution {
4 public int minPairSum(int[] nums) {
5 Arrays.sort(nums);
6 int maxSum = 0;
7 for (int i = 0; i < nums.length / 2; i++) {
8 int pairSum = nums[i] + nums[nums.length - 1 - i];
9 maxSum = Math.max(maxSum, pairSum);
10 }
11 return maxSum;
12 }
13
14 public static void main(String[] args) {
15 Solution sol = new Solution();
16 int[] nums = {3, 5, 2, 3};
17 System.out.println("Output: " + sol.minPairSum(nums)); // Output should be 7
18 }
19}This Java solution sorts the array with Arrays.sort and uses basic loop constructs to pair elements and find 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#include <vector>
#include <algorithm>
int minPairSum(std::vector<int>& nums) {
std::sort(nums.begin(), nums.end());
int maxSum = 0, pairSum;
for (size_t i = 0; i < nums.size() / 2; ++i) {
pairSum = nums[i] + nums[nums.size() - 1 - i];
maxSum = std::max(maxSum, pairSum);
}
return maxSum;
}
int main() {
std::vector<int> nums = {3, 5, 2, 3};
int result = minPairSum(nums);
std::cout << "Output: " << result << std::endl;
return 0;
}The solution divides and conquers by directly selecting indices from ends towards the center of the sorted vector, essentially making direct index-based pairings.