Problem

Given an integer array nums of 2n integers, group these integers into n pairs (a1, b1), (a2, b2), ..., (an, bn) such that the sum of min(ai, bi) for all i is maximized. Return the maximized sum.

Examples

Example 1

1
2
3
4
5
6
7

Input: nums = [1,4,3,2]
Output: 4
Explanation: All possible pairings (ignoring the ordering of elements) are:
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
So the maximum possible sum is 4.

Example 2

1
2
3

Input: nums = [6,2,6,5,1,2]
Output: 9
Explanation: The optimal pairing is (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9.

Constraints

  • 1 <= n <= 10^4
  • nums.length == 2 * n
  • -10^4 <= nums[i] <= 10^4

Solution

Method 1 – Sorting and Pairing

Intuition

To maximize the sum of the minimums of pairs, we should pair the smallest numbers together. By sorting the array and pairing every two consecutive elements, we ensure that each pair’s minimum is as large as possible, maximizing the total sum.

Approach

  1. Sort the input array nums in non-decreasing order.
  2. Initialize a variable ans to store the result.
  3. Iterate through the sorted array, adding every element at even indices (0, 2, 4, …) to ans.
  4. Return ans as the maximized sum.

This works because, after sorting, pairing each number with its immediate next ensures the minimum in each pair is as large as possible.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
  int arrayPairSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int ans = 0;
    for (int i = 0; i < nums.size(); i += 2) {
      ans += nums[i];
    }
    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
  public int arrayPairSum(int[] nums) {
    Arrays.sort(nums);
    int ans = 0;
    for (int i = 0; i < nums.length; i += 2) {
      ans += nums[i];
    }
    return ans;
  }
}
1
2
3
4
5
6
7

class Solution:
  def arrayPairSum(self, nums: list[int]) -> int:
    nums.sort()
    ans: int = 0
    for i in range(0, len(nums), 2):
      ans += nums[i]
    return ans

Complexity

  • ⏰ Time complexity: O(N log N) (due to sorting)
  • 🧺 Space complexity: O(1) (if sorting in-place), otherwise O(N) depending on the language’s sort implementation