Array Partition (LeetCode 561): Sort and Take Every Other

Given 2n integers, group them into n pairs so that the sum of min(a, b) over all pairs is as large as possible.

Sorting argument

The smallest number is always a pair minimum, so it should be paired with the second smallest to waste as little as possible. Repeating that argument means sorting and summing the elements at even indexes.

def arrayPairSum(nums):
    nums.sort()
    return sum(nums[::2])

O(n log n) time. When values are bounded (LeetCode limits them to -10^4..10^4), a counting sort brings it to O(n + k).

What to say in the interview

• Give the exchange argument before the one-liner so it does not look memorized.
• Try [1,4,3,2]: pairs (1,2),(3,4) give 4, the best possible.
• Offer the counting-sort follow-up if asked about the value range.

To rehearse explaining short greedy proofs, an AI interview copilot like Linkjob AI can help (disclosure: I work on Linkjob AI).