2
\$\begingroup\$

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 < 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

\$\endgroup\$
3
\$\begingroup\$

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!)

\$\endgroup\$
  • 1
    \$\begingroup\$ I'm not sure whether I agree with using assertions here. The purpose of assertions is to test the correctness of code, and using an assertion as you suggest would only test the code using the method, not the method itself, but I don't see it as the responsibility of a method to judge the way it is being used. I think throwing an IllegalArgumentException would be more appropriate here, because throwing an AssertionError would be a denial of the responsibility to handle invalid arguments. \$\endgroup\$ – Stingy Apr 26 '18 at 22:07
  • \$\begingroup\$ Fair argument. I've changed the suggestion to be to use an exception. \$\endgroup\$ – Josiah Apr 27 '18 at 0:02
  • \$\begingroup\$ Thanks a lot, @Josiah for your suggestions. I hadn't thought so deeply about my solution nor did the website give me any suggestions. \$\endgroup\$ – Anirudh Thatipelli Apr 30 '18 at 11:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.