Java Solution, Sorting. And rough proof of algorithm.


  • 88

    The algorithm is first sort the input array and then the sum of 1st, 3rd, 5th..., is the answer.

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

    Let me try to prove the algorithm...

    1. Assume in each pair i, bi >= ai.
    2. Denote Sm = min(a1, b1) + min(a2, b2) + ... + min(an, bn). The biggest Sm is the answer of this problem. Given 1, Sm = a1 + a2 + ... + an.
    3. Denote Sa = a1 + b1 + a2 + b2 + ... + an + bn. Sa is constant for a given input.
    4. Denote di = |ai - bi|. Given 1, di = bi - ai. Denote Sd = d1 + d2 + ... + dn.
    5. So Sa = a1 + a1 + d1 + a2 + a2 + d2 + ... + an + an + di = 2Sm + Sd => Sm = (Sa - Sd) / 2. To get the max Sm, given Sa is constant, we need to make Sd as small as possible.
    6. So this problem becomes finding pairs in an array that makes sum of di (distance between ai and bi) as small as possible. Apparently, sum of these distances of adjacent elements is the smallest. If that's not intuitive enough, see attached picture. Case 1 has the smallest Sd.
      0_1492961937328_leetcode561.jpg

  • 1

    C++ version

    // OJ: https://leetcode.com/problems/array-partition-i
    // Author: github.com/lzl124631x
    // Time: O(NlogN)
    // Space: O(1)
    class Solution {
    public:
      int arrayPairSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int sum = 0;
        for (int i = 0; i < nums.size(); sum += nums[i], i += 2);
        return sum;
      }
    };
    

  • 0

    same as mine.
    I really hope there's a better solution.
    But I haven't found yet.


  • 0
    L

    I think that's the right solution. I'm using the same approach but stupid me..... I write a quick sort by myself instead of using the Arrays.sort method. >.<


  • 0
    S

    thanks for your solution and your prove


  • 0
    T

    thanks for your explicit description!:)


  • 1
    S

    @Vick.Chen you can use counting sort (O(n)) instead of Arrays.sort(), which is O(nlog(n))

    public int arrayPairSum(int[] nums){

    	 int [] counts = new int [20001];
    	 for(int i=0;i<nums.length;i++){
    		 counts[nums[i]+10000]++;
    	 }
    	 
    	 
    	 int cnt = 0;
    	 int prevCnt = 0;
    	 int res=0;
    	 for(int i=0; i<counts.length;i++){
    		 if(counts[i]==0)
    			 continue;
    		 prevCnt = cnt;
    		 cnt +=counts[i];
    	
    		 if ((prevCnt & 1)!=0){//uneven
    			 counts[i]--;
    		 }
    		 if((counts[i] & 1) == 0) {//even
    			res+=(i-10000)*counts[i]/2; 
    		 }
    		 else{
    			 res+=(i-10000)*(counts[i]/2+1);
    		 }
    	
    	 }
    	 return res;
      }

  • 0

    When I think about this problem, the intuition tells me to pair small numbers as many as possible so that large numbers would not be sacrificed in Math.min operation. Thanks for your sharing and proof!


  • 0
    M

    Thank you for your detailed explanation!


  • 0
    L

    For two pairs (a1,b1) and (a2,b2), suppose a<b.
    if b1>a2, we can always swap b1 and a2 to get a larger Min which is a1+a2.
    Same situation when we have more pairs.


  • 0
    Y

    @shunti counting sort requires k+n operations, where k is the size of the input set {a1,a2,...,an}. Technically speaking, since we don't know the number k, it's not rigorous enough to state the sort is in O(n).


  • 0
    S

    @yufan4 If your input set is {a1,a2,...,an} then it's size is n (not k). Counting sort is O(n) since it touches each element of the input set exactly one time (which is the first loop of the code)
    for(int i=0;i<nums.length;i++){
    counts[nums[i]+10000]++;
    }


  • 0
    Y

    @shunti yep, but the second loop requires counts.length operations, that's where the k comes from. given an array of size 3, say [1,2,3], it would be more efficient to use a regular sorting algorithm rather than to use the counting sort. Thanks!


  • 0
    S

    @yufan4 : Well,you cannot have input of size 3 here:) (input size is even number in the problem)

    But I agree with you that for small input sizes, Arrays.sort() would be faster. However, when the input size is larger, approach with counting sort would be faster than Arrays.sort(), since asymptotically O(n) is faster than O(nlogn).

    Now for this problem, the question is what is the value for that threshold (from which approach with counting sort is faster) and whether this threshold belongs to range of the given input sizes ([2,20000]).

    The second loop simply adds elements at the even indices in the previously sorted array,
    and it has 20,001 iterations.

    To get rough estimate, i will take the "worst case" for the second loop: in the input array,
    each element is seen exaclty one time. So n times (n<=20,000) loop has either 6 or 7 lines of computations(50% - 6 lines and 50% -7 lines), and it has only 2 lines to execute (20,001-n) times.
    Here I do ignore cost of each operation, but array access is generally more expensive than basic arithmetic operations, so for each line I will count array accesses.
    We have only 1 array access for (20,001-n) times, and for n times - at most 6 array accesses; thus, the second loop has 6n+(20,001-n) = 5n + 20,001 array accesses

    Now I compare nlogn+n/2 (approach with Arrays.sort()) and 3n+5n+20,001 = 8n+20,001
    (there are 3 array accesses per each iteration in the first loop, and I do ignore constant for nlogn for Arrays.sort())

    This rough calculations give us that for n>=4748, approach with counting sort is faster than the approach with Arrays.sort(), which is in the range of the problem ([2, 20000])

    Obviously, one can benchmark both approaches on his/her machine(to take into account cost of each operation on his/her platform), and empirically estimates this threshold.

    Which approach is better is clearly depends on what the expected input sizes are, and it could be beneficial just to switch between the approaches based on value of n (if arrays of small sizes are also expected).

    On Leetcode tests, i got 38ms for the approach with Arrays.sort() and 19ms for the approach with counting sort.


  • 0
    G

    same!same!but the math of the code is worth to dig and think。


  • 0
    P
    This post is deleted!

  • 0
    L

    the method is great, and i think why sort the array the the sum(array[i]) (i = i + 2) can get the min sd because between two points the straight line is shortest. all the element in the array equal a point in X axis


  • 0
    R

    same with mine,but why so slow? because of comparing to c++?


  • 0
    P

    Nice solution..

    below is mine..

    public class Solution {
    public int arrayPairSum(int[] nums) {
    Arrays.sort(ar);
    int l=0,h=ar.length-1;
    int max=0;
    while(l<=h){
    max += Math.min(ar[l], ar[l+1]);
    l=l+2;
    }
    return max;
    }
    }


  • 0
    R

    I think it can be proved with mathematical induction. When n is 4, it is trivial. Assume When n is k, this algorithm is correct. When n is k+2, assume the ascending order a1, a2, ...ak+2. If we do not make the last two elements a pair, they each match an element ai, aj, where i and j <= k and ai<aj. If we do not consider aj, the remaining sum of minimum is a possible sum of minimum for a1, a2, ...ak and is not the optimal solution for n being k. Since aj is less than ak+1, the method separate the last two elements is not optimal. So we have to pair the last two and the remaining is solved with our method by assumption.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.