LeetCode 561: Array Partition (Sort + Pair Min Sum)

Today we solve LeetCode 561 - Array Partition.

Source: https://leetcode.com/problems/array-partition/

English

Problem Summary

Given an integer array nums of length 2n, split it into n pairs so that the sum of min(pair) is maximized.

Key Insight

After sorting, the best strategy is to pair adjacent numbers: (a0,a1), (a2,a3), .... Then each pair minimum is exactly the element at even index, and this arrangement maximizes the total of minima.

Why This Greedy Works

If a small number is paired with a far larger number while another close number is left for a different pair, we waste potential minimum value. Sorting and adjacent pairing prevents that waste. So we can directly add elements at indices 0,2,4,....

Algorithm

1) Sort nums in nondecreasing order.
2) Initialize sum = 0.
3) For every even index i, add nums[i] to sum.
4) Return sum.

Complexity Analysis

Time: O(n log n) due to sorting.
Space: O(1) extra if in-place sort (language/runtime dependent).

Common Pitfalls

- Trying to brute-force all pairings (combinatorial explosion).
- Sorting descending and adding wrong indices.
- Off-by-one loop mistakes when stepping by 2.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

import java.util.Arrays;

class Solution {
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int sum = 0;
        for (int i = 0; i < nums.length; i += 2) {
            sum += nums[i];
        }
        return sum;
    }
}

import "sort"

func arrayPairSum(nums []int) int {
    sort.Ints(nums)
    sum := 0
    for i := 0; i < len(nums); i += 2 {
        sum += nums[i]
    }
    return sum
}

class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int sum = 0;
        for (int i = 0; i < (int)nums.size(); i += 2) {
            sum += nums[i];
        }
        return sum;
    }
};

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        nums.sort()
        return sum(nums[::2])

var arrayPairSum = function(nums) {
  nums.sort((a, b) => a - b);
  let sum = 0;
  for (let i = 0; i < nums.length; i += 2) {
    sum += nums[i];
  }
  return sum;
};

中文

题目概述

给你一个长度为 2n 的整数数组 nums，要把它拆成 n 对，目标是让每对最小值之和最大，返回这个最大和。

核心思路

先排序，然后相邻两两配对：(a0,a1), (a2,a3), ...。每一对的最小值就是偶数下标元素，因此答案就是所有偶数下标元素之和。

贪心正确性直觉

如果把一个较小数和很大的数配在一起，通常会让另一个配对的最小值变小，造成损失。排序后相邻配对，能够尽量“保住”每一对的最小值，总和最优。

算法步骤

1）对 nums 升序排序。
2）初始化 sum = 0。
3）遍历偶数下标 0,2,4,...，累加 nums[i]。
4）返回 sum。

复杂度分析

时间复杂度：O(n log n)（排序开销）。
空间复杂度：O(1) 额外空间（取决于具体排序实现）。

常见陷阱

- 误用暴力枚举所有配对，复杂度过高。
- 排序后取错下标（应取偶数位）。
- 循环步长不是 2，导致重复或遗漏。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

import java.util.Arrays;

class Solution {
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int sum = 0;
        for (int i = 0; i < nums.length; i += 2) {
            sum += nums[i];
        }
        return sum;
    }
}

import "sort"

func arrayPairSum(nums []int) int {
    sort.Ints(nums)
    sum := 0
    for i := 0; i < len(nums); i += 2 {
        sum += nums[i]
    }
    return sum
}

class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int sum = 0;
        for (int i = 0; i < (int)nums.size(); i += 2) {
            sum += nums[i];
        }
        return sum;
    }
};

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        nums.sort()
        return sum(nums[::2])

var arrayPairSum = function(nums) {
  nums.sort((a, b) => a - b);
  let sum = 0;
  for (let i = 0; i < nums.length; i += 2) {
    sum += nums[i];
  }
  return sum;
};