2
\$\begingroup\$

I asked one question on code review yesterday about my code style, logic and readability of code. Hence, today I kept all those suggestions in mind while solving a new problem question.

The question is such: Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example: given array S = {-1 2 1 -4}, and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

This is my solution:

 public int threeSumClosest(int[] num, int target) {
    if(num.length < 3) {
        return 0;
    }
      Arrays.sort(num);
    int tempSum = Math.abs( target - ( num[0] + num[1] + num[2] ));
    int result = num[0] + num[1] + num[2];

    for (int index = 0; index < num.length - 1; index++) {
        int j = index + 1;
        int k = num.length-1;
        while (j < k){
            int newSum = Math.abs( target - ( num[index] + num[j] + num[k] ) );
            if( newSum == 0 ) {
                return ( num[index] + num[j] + num[k] ) ;
            }
            else if ( num[index] + num[j] + num[k] < target ) {
                if( newSum < tempSum ) {
                    tempSum = newSum;
                    result = num[index] + num[j] + num[k];
                }

                j++;
            }
            else {
                if( newSum < tempSum ) {
                    tempSum = newSum;
                    result = num[index] + num[j] + num[k];
                }
                k--;
            }
        }//end of while loop
    }// end of for loop
    return result;
}

It would be great to hear back if I need to make further improvements. Any help will be highly appreciated. Also, Is there an approach which can solve this problem in less than \$O(n^2)\$.

\$\endgroup\$
4
\$\begingroup\$

Algorithm - Reducing search space

I'd define kMax as num.length - 1.

Then, do a binary search for the point at which num[0] + num[1] + num[k - 1] is too low, and num[0] + num[1] + num[k] is too high. Set kMax to k.

Next, do a binary search for the point at which num[i] + num[kMax - 1] + num[kMax] is too high, and num[i - 1] + num[kMax - 1] + num[kMax] is too low. Define iMin to be i - 1.

Start your for loop loop with index at iMin. At the start of each iteration, set k to kMax.

Instead of your current moving up/moving down scheme, just start downing k. As long as [i][j][k-1] is too high, kMax = k. When [i][j][k-1] is no longer too high, resume your uppy-downy scheme.

Whenever you increment i, check if [i][k-1][k] is too low. If so, increase i until [i][k-1][k] is no longer too low. Check if [i-1][k-1][k] gives a better match and store it as temp.

AFter changing scope like this, check the opposite end of the scope. So if you just reduced k, check if [i][k-1][k] is too low. If you just increased i, check if [i][i+1][k] is too high. Do this until scope is stable.

Perhaps binary search could speed this (upping i and downing k) up too, but I'm not sure.

What this would do is potentially eliminate is a lot of your search space.

You see, if I gave you the number 42 to find in an array that contained random numbers between -500 and +200, -500, +199, +200 is simply too low. So you can kill off any number that's below -357, provided it's not the last number at or below -357.

This is a reduction of 20% of your search space with a simple binary search.

Additionally, once we get to -70, any number greater than 182 that is not the last number at or above 182 is not going to help.


Binary search is blazingly fast. 10000 elements can be searched through in 13-14 array accesses. 100000 elements - 17 array accesses.

Consider stopping binary search when your scope size is less than 128 (your code should go blazingly fast at that point anyway).

Your code

for (int index = 0; index < num.length - 1; index++)

For an array of 3 elements... index < num.length - 1 means index < 3 - 1 means index < 2.

So you've got a problem; You'll eventually check [1][2][2]. Your fix for this is while(j < k), but I think you'll be better served by changing the for loop header to be for (int index = 0; index < num.length - 2; index++) (changing index < num.length - 1 to index < num.length - 2). And then adding a comment WHY it is 2.

        int newSum = Math.abs( target - ( num[index] + num[j] + num[k] ) );
        if( newSum == 0 ) {
            return ( num[index] + num[j] + num[k] ) ;
        }
        else if ( num[index] + num[j] + num[k] < target ) {
            //code
            result = num[index] + num[j] + num[k];

You have here, in a single iteration, 2 to 3 summations of num[index] + num[j] + num[k]. Some languages will cache these values. Some languages will not. I'd get in the habit of summing them once, then doing what you must.

        else if ( num[index] + num[j] + num[k] < target ) {
            if( newSum < tempSum ) {
                tempSum = newSum;
                result = num[index] + num[j] + num[k];
            }

            j++;
        }
        else {
            if( newSum < tempSum ) {
                tempSum = newSum;
                result = num[index] + num[j] + num[k];
            }
            k--;
        }

Haaang on.

I think you can unduplicate your code here:

        else {
            if( newSum < tempSum ) {
                tempSum = newSum;
                result = num[index] + num[j] + num[k];
            }
            if(num[index] + num[j] + num[k] < target){
                k--;
            } else {
                j++;
            }
        }

Combine it with the idea of making the sum variable and you get the following:

        int sum = num[index] + num[j] + num[k];
        if( sum == 0 ) {
            return sum;
        }
        else {
            int newSum = Math.abs( target - sum );                
            if( newSum < tempSum ) {
                tempSum = newSum;
                result = sum;
            }
            if(sum < target){
                k--;
            } else {
                j++;
            }
        }

Additionally, Math.abs is not yet required for your first if. So leaving that one out until it's needed speeds things up a bit.

And since a return statement exits the function, we can use an implicit else:

        int sum = num[index] + num[j] + num[k];
        if( sum == 0 ) {
            return sum;
        }
        int newSum = Math.abs( target - sum );                
        if( newSum < tempSum ) {
            tempSum = newSum;
            result = sum;
        }
        if(sum < target){
            k--;
        } else {
            j++;
        }
\$\endgroup\$
2
\$\begingroup\$

Looking at the first bit of code:

if(num.length < 3) {
        return 0;
    }

Naming

  • minimumInputArrayLength = 3 and would be helpful to someone skimming the code.

  • inputArray is probably a more descriptive name than num.

Magic Numbers

The immediate caller has to handle what is essentially an exception and to handle it in a form other than try...catch. It also precludes the caller from allowing the exception to bubble up to what may be a more appropriate higher level.

All the worse because there's no way to distinguish a good zero from a bad zero.

For example: given an array S = {-1 2 1 -3}, and target = 1:

  • result could be zero at the end of the computation.

A little less worse, but still a potential source of cognitive overhead for the programmer using the function:

  • result could be 2 at the end of the computation depending on the behavior of the sort function.

  • A specification would help, but probably not be consulted until bugs were experienced.

Down the road, the dependency on sorting by < or > ought to be made explicit so that a maintainer of the code is less likely to change it and thereby breaking code that depends on implementation details.

\$\endgroup\$

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.