Problem Description
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.
Key Insights
- Pairing the smallest numbers together maximizes the total sum of the minimums.
- Sorting the array allows us to simply take every second element starting from the first to compute the desired sum.
- The greedy approach works efficiently due to the constraints.
Space and Time Complexity
Time Complexity: O(n log n) - due to the sorting step.
Space Complexity: O(1) - we use a constant amount of extra space.
Solution
To solve this problem, we can sort the input array and then iterate through the sorted array, taking every second element starting from the first element. This ensures that we are always summing the minimum of each pair formed by adjacent elements in the sorted array. The greedy approach of sorting followed by summing the appropriate elements guarantees that we maximize the sum of the minimum values.