Find two values that add up to the sum

Question

I was working on a practice Java exam online:

Write a function that, given a list and a target sum, returns zero-based indices of any two distinct elements whose sum is equal to the target sum. If there are no such elements, the function should return null. For example, findTwoSum(new int[] { 1, 3, 5, 7, 9 }, 12) should return a single dimensional array with two elements and contain any of the following pairs of indices:

1 and 4 (3 + 9 = 12)
2 and 3 (5 + 7 = 12)
3 and 2 (7 + 5 = 12)
4 and 1 (9 + 3 = 12)

Here is my solution:

public class TwoSum {

    public static int[] findTwoSum(int[] list, int sum) {
        int[] twoSum = null;
        if(list != null){
            int listSize = list.length;
            int mod = listSize % 2;
            int half = listSize/2;
            int stop = mod > 0 ? half+1 : half;
            if(listSize >= 2){
                outer: for(int currentIndex=0; currentIndex<listSize; currentIndex++){
                            if(currentIndex == stop){
                                break;
                            }
                            for(int otherIndex=0; otherIndex<listSize; otherIndex++){
                                if(currentIndex < otherIndex){
                                    int current = list[currentIndex];
                                    int other = list[otherIndex];
                                    int currentSum = current + other;
                                    if(currentSum == sum){
                                        twoSum = new int[]{currentIndex, otherIndex};
                                        break outer;
                                    }
                                }
                            }
                        }
            }
        }
        return twoSum;
    }

    public static void main(String[] args) {
        int[] indices = findTwoSum(new int[] { 1, 3, 5, 7, 9 }, 12);
        System.out.println(indices[0] + " " + indices[1]);
    }
}

My code passed all the unit tests, however, they have another check for a large list, and apparently my code runs too slow when the list size grows. Apart from me trying to decipher what their definition of too slow is, simply put, are there any optimizations I can make to have my code run faster? I tried to find the 'tipping point' in comparing numbers where I could stop checking, and I added that optimization, but apparently, that isn't good enough.

Answer 1

I would find this easier to read if the first thing in the method was

        if (list == null || list.length < 2) {
            return null;
        }

This gets rid of the unlikely cases off the bat and saves us having to indent the rest of the logic inside two if statements.

            int listSize = list.length;
            int mod = listSize % 2;
            int half = listSize/2;
            int stop = mod > 0 ? half+1 : half;

This could just be

            int stop = (list.length + 1) / 2;

You never use mod or half elsewhere and can just replace listSize with list.length. This will return the same results, as if the list has an odd size, adding one will give it an even size. Then dividing by two will return the same result as half + 1, since half is rounded down. If even, then adding one before dividing by two does nothing, as the odd number will be rounded down.

                outer: for(int currentIndex=0; currentIndex<listSize; currentIndex++){
                            if(currentIndex == stop){
                                break;
                            }

This could just be

          for (int currentIndex = 0; currentIndex < stop; currentIndex++) {

Although either way it returns an incorrect result for an input like

new int[] { 1, 2, 9, 5, 7 }, 12

You do

                                    int current = list[currentIndex];

inside the inner loop.

Do it before the inner loop instead. Then you can just do it once rather than once for each iteration of the inner loop. On the bright side, the compiler probably compiled this out anyway.

                                        twoSum = new int[]{currentIndex, otherIndex};
                                        break outer;

This could be just

                            return new int[]{currentIndex, otherIndex};

Then you don't need the labeled loop. And

        return twoSum;

could be just

        return null;

No need for the twoSum variable at all.

Alternatives

This is an \$\mathcal{O}(n^2)\$ solution. But this problem is solvable in linear time. Consider

public static int[] findTwoSum(int[] numbers, int target) {
    if (numbers == null) {
        return null;
    }

    Integer[] complements = new Integer[target];

    for (int i = 0; i < numbers.length; i++) {
        if (complements[numbers[i]] != null) {
            return new int[]{complements[numbers[i]], i};
        }

        complements[target - numbers[i]] = i;
    }

    return null;
}

This works fine for modest sums where all the inputs are positive (like your example). It will be much faster for large inputs.

If those constraints don't work for you, try

public static int[] findTwoSum(int[] numbers, int target) {
    if (numbers == null) {
        return null;
    }

    Map<Long, Integer> complements = new HashMap<>();

    for (int i = 0; i < numbers.length; i++) {
        Integer complementIndex = complements.get((long)numbers[i]);
        if (complementIndex != null) {
            return new int[]{complementIndex, i};
        }

        // it's possible that for large targets and a negative input
        // that we might overflow the int type
        long complement = (long)target - numbers[i];
        complements.put(complement, i);
    }

    return null;
}

Now it doesn't matter if the target sum is large or some of the numbers are negative.

Either version works by storing the locations of the complements for each value. We only need to loop once and get/put are constant time operations for a HashMap.

Answer 2

In the following, I am going to propose a few alternative, simpler notations for single statements in your code, even though some of these examples will be irrelevant after following mdfst13's suggestions because they can be replaced together with other statements by one, simpler statement.

• First, let's take this line:

  int stop = mod > 0 ? half+1 : half;
  

  Since mod can only be either 0 or 1, the above statement can be rewritten as:

  int stop = half + mod;
  

• Also, the declarations of mod, half and stop could be inside the if(listSize >= 2) clause, seeing as they have no relevance outside it.

• Your inner for loop can be written as:

  for(int otherIndex=currentIndex + 1; otherIndex<listSize; otherIndex++) {
      // ...
  }
  

  This eliminates the need for the if-clause inside it.

• mdfst13 has already provided a test case where your program fails, so I'll just point out the mistake in your logic for the sake of completeness. There is no reason to believe that, if a pair of numbers exists in the array that sums up to a given number, one of the two numbers must be in the first half of the array. First of all, there is no guarantee that the array is even sorted. And second, even if it were sorted, this doesn't mean that the middle element in the array (or the leftmost element of the right half, if the number of elements is odd) is equal to or greater than the half of the given number. Consider this array: [6,7,8,9,10,11], and the number 21. I think this demonstrates the flaw in your logic quite clearly. What you probably meant to do is iterate through the array until you encounter a number that is equal to or greater than the half of the sum-number. But even then, you'd have to make sure that the array is sorted first.

  For implementing such an algorithm, the binarySearch methods from the Arrays class could prove useful:

  /**
   * A helper class to facilitate the use of the binary search methods of the
   * {@code Arrays} class when searching for an {@code int} in an array where
   * every number of that array is bound to another {@code int} (in this case,
   * an index in another, unsorted array).
   */
  private static class NumberWithIndex implements Comparable<NumberWithIndex> {
  
      /**
       * This field is non-final so that a search template can be used and a
       * new object does not have to be created for every search
       */
      private int number;
  
      /**
       * This field is ignored in equals, hashCode and compareTo
       */
      private final int index;
  
      NumberWithIndex(int number, int index) {
          this.number = number;
          this.index = index;
      }
  
      void setNumber(int number) {
          this.number = number;
      }
  
      int getNumber() {
          return number;
      }
  
      int getIndex() {
          return index;
      }
  
      @Override
      public int hashCode() {
          return number;
      }
  
      @Override
      public boolean equals(Object obj) {
          if (this == obj) {
              return true;
          }
          if (!(obj instanceof NumberWithIndex)) {
              return false;
          }
          final NumberWithIndex other = (NumberWithIndex) obj;
          return this.number == other.number;
      }
  
      @Override
      public int compareTo(NumberWithIndex o) {
          return this.number - o.number;
      }
  }
  
  public static int[] findTwoSum(int[] numbers, int target) {
      NumberWithIndex[] numbersWithOriginalIndexesSorted = new NumberWithIndex[numbers.length];
      for (int i = 0; i < numbers.length; i++) {
          numbersWithOriginalIndexesSorted[i] = new NumberWithIndex(numbers[i], i);
      }
      Arrays.sort(numbersWithOriginalIndexesSorted);
  
      NumberWithIndex searchTemplate = new NumberWithIndex(0, 0);
      // index of searchTemplate is irrelevant, 0 is completely arbitrary
  
      for (int i = 0;
              i < numbersWithOriginalIndexesSorted.length
              && numbersWithOriginalIndexesSorted[i].getNumber() <= target / 2;
              i++) {
  
          searchTemplate.setNumber(target - numbersWithOriginalIndexesSorted[i].getNumber());
  
          int j = Arrays.binarySearch(
                  numbersWithOriginalIndexesSorted,
                  i + 1,
                  numbersWithOriginalIndexesSorted.length,
                  searchTemplate);
  
          if (j >= 0) {
              return new int[]{
                  numbersWithOriginalIndexesSorted[i].getIndex(),
                  numbersWithOriginalIndexesSorted[j].getIndex()
              };
          }
      }
      return null;
  }
  

  This basically does what you presumably intended to do originally, but since it takes advantage of native methods like the binary search algorithms, it is probably much faster than your original code.

Update

I've refined the code that demonstrates the usage of the binary search algorithm provided by the Arrays class. Instead of simply creating a copy of the original array, sorting that copy, finding a number pair from that sorted copy and then iterating through the original array to get the indexes, the updated code binds the original indexes to the numbers prior to sorting them. Unfortunately, this cannot be done with a Map.Entry<Integer, Integer>, because then it would not be possible to use the binary search methods in Arrays, since, for one thing, a Map.Entry is not comparable, and for another, its equals(Object) method also takes into account the entry's value, which in our case would represent the index in the original array, which is irrelevant when just searching for the numbers. It is therefore necessary to design a helper class that ignores the index the numbers are bound to in its equals and compareTo methods. This might seem convoluted, but from a purely programming-logical point of view, this is the most elegant solution I can think of for your algorithm (note that there might still be faster algorithms – I'm just trying to optimize the implementation of your algorithm).