Array partition 1 to group the array into pairs and make sum of minimum of pairs as maximum Challenge from LeetCode: Array Partition I


  Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), ..., (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.
  
  Example 1:
  
  Input: [1,4,3,2]
  
  Output: 4
  
  Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).


My approach:

import java.util.*;

class Solution {
    public int arrayPairSum(int[] nums) {
       //Sorting the array in least time
        Arrays.sort(nums);

        int sum = 0;
        for( int i = 0; i &lt; nums.length; i = i + 2 )
            sum += nums[i];

        return sum;

    }
}


1) Is there a better way to solve this question?

2) Can I still decrease the time and space complexity?

Reference
Your logic is correct. You need each pair to include numbers as close as possible together, so that when you sacrifice each big number in the pair, the little number that survives is as large as possible while still being small enough to be shielded by the big number. The obvious way to pair up numbers like that is to sort them, and for the problem you've describe the language library sorting algorithm is probably the best choice. 

There are still a few things that want cleaning up with this solution. 

First, you are mutating your input array by sorting it. That is probably an undesirable side effect for this function, and should be avoided. 

Second, it is often worth checking promised preconditions that you're relying on are actually honoured by whoever is using the function. This is where exceptions are useful. For example, I would check that the length of the input array is even.

Third, it is generally undesirable to use the import something.* form because it leads to confusion about where things are coming from. 



Following the link, there is a further guarantee that 


  n is a positive integer, which is in the range of [1, 10000]. All the
  integers in the array will be in the range of [-10000, 10000].


An array of size 20000 is plausible to hold in memory. This means that Counting sort is a plausible alternative to the sort from the Language library, and it has time complexity linear in the range of possible values, whereas the quicksort implementation used by Java is loglinear in the number of elements. (You don't have to unpack the count bins back into a sorted array, but can directly work out the pairs and smaller of the pairs)

In practice for the input constraints given I would still expect the quicksort to be faster and all round cheaper. However, I don't have any profiling on that; it's just a guess. Further, if the range of possible integers was very much smaller or the value of n was very much larger, implementing a counting approach would probably work well. 

(Strictly speaking because, as above, you'd need to copy the input array to avoid mutating your input with a sort, given n is larger than the range of the values, an array of counts would be cheaper in terms of space too!)