Problem Description
Given an integer array nums of 2n integers, group these integers into n pairs such that the sum of min(a, b) for each pair is maximized. Return the maximized sum.
Key Insights
- Sorting the array puts numbers in ascending order, which enables pairing the smallest numbers together.
- Pairing consecutive elements guarantees that each pair's minimum is as high as possible.
- For integers in a fixed range, counting sort can be used for optimal performance.
Space and Time Complexity
Time Complexity: O(n log n) due to sorting (O(n) if using counting sort on a fixed range).
Space Complexity: O(1) or O(n) depending on the sorting algorithm used.
Solution
The solution works by first sorting the nums array. Once sorted, pairing each element at even indices with its immediate neighbor ensures that the smaller element of each pair is as large as possible given the constraints. This approach maximizes the overall sum of the minimums from each pair. The main trick is to recognize that, after sorting, the optimal pairing is simply consecutive elements.