Assume there is an array:

a1 < a2 < a3 < a4 ...... < a2n

sum = ?

As we all known, a1 = min(a1, ai) (1 < i <= 2n).

So the sum which we want to figure out must include the smallest number a1. When we remove a1 from the given array, which number do you want to killed at the same time? As far as I see, the best answer is a2.

a3 < a4 < a5 < a6.... < a2n

sum = a1 + ?

Now, a3 is the smallest number of array!

I believe you have already know all story here.

a5 < a6 < a7 < ... < a2n

sum = a1 + a3 + ?

...

sum = a1 + a3 + .... + a(2n - 1)

My first solution:

```
public 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;
}
}
```

Since we know the range of array's integers, bucket sort is a faster sort algorithm.

```
public class Solution {
public int arrayPairSum(int[] nums) {
int[] array = new int[20001];
for (int i = 0; i < nums.length; i++) {
array[nums[i] + 10000]++;
}
int sum = 0;
boolean smaller = true;
for (int i = 0; i < array.length;) {
if (array[i] > 0) {
if (smaller) {
sum += i - 10000;
}
smaller = !smaller;
array[i]--;
} else {
i++;
}
}
return sum;
}
}
```