Array Partition - Video Solutions

Problem Overview: You receive an array of 2n integers. The task is to form n pairs so that the sum of the minimum value in each pair is maximized. The trick is realizing that pairing decisions affect which numbers become the minimums contributing to the final sum.

Approach 1: Sorting and Pairing Strategy (Time: O(n log n), Space: O(1) or O(log n) depending on sort)

The simplest and most reliable strategy is to sort the array first. Once sorted, pair adjacent elements: (nums[0], nums[1]), (nums[2], nums[3]), and so on. The key insight is that in each pair, the smaller element contributes to the sum. Sorting ensures that small numbers are grouped together instead of being wasted as the minimum in pairs with very large numbers. After sorting, iterate through the array and add every element at an even index (0, 2, 4...) to the result. Sorting dominates the runtime at O(n log n), while the pairing scan is linear. This approach uses concepts from Sorting and a simple Greedy strategy.

Approach 2: Greedy Pairing with Counting Sort Optimization (Time: O(n + k), Space: O(k))

The constraints guarantee that numbers fall within a limited range (typically -10000 to 10000). Instead of sorting with comparison-based algorithms, build a frequency array and simulate a Counting Sort. Iterate through the frequency array in increasing order and track whether the current number should be included in the sum or skipped. Every second element encountered becomes the minimum of a pair and is added to the result. This effectively recreates the sorted order without performing an explicit sort. The complexity becomes O(n + k), where k is the numeric range. This method leverages Counting Sort and still follows the same greedy observation: maximize the contribution of smaller numbers by pairing them early.

Recommended for interviews: The sorting approach is the expected solution in most interviews. It is easy to reason about and clearly demonstrates the greedy insight that pairing adjacent numbers in sorted order maximizes the sum of pair minimums. The counting sort optimization shows deeper awareness of constraints and can reduce runtime to linear when the value range is bounded. Mentioning both approaches shows strong algorithmic judgment.