Find pairs in an integer array whose sum is equal to 10

Question

I came up with 2 different solutions in Java.

First one is:

public static void main(String[] args) {


    int[] array = new int[]{10,3,4,6,1,9,10,0};
    int sum=0;

    for (int i=0;i<array.length;i++)
    {
      for (int j=i ; j<array.length;j++){


        sum = array[i] + array[j];
        if (sum==10){

          System.out.println(array[i] + " " + array[j]);

        }


      }

    }

I believe this one works in \$O(N^2)\$.

My second solution is:

  public static void main(String[] args) {
    int[] nums = new int[] {10, 3, 4, 6, 1, 9, 10, 0};
    Hashtable<Integer, Integer> reqNoList = new Hashtable<Integer, Integer>();
    int sum = 10;
    int i = 0, count = 0;

    while (i < nums.length && i < sum) {
      int key = sum - nums[i];
      if (reqNoList.containsKey(nums[i])) {
        Integer temp = reqNoList.get(nums[i]);
        System.out.println(key + " " + nums[i]);
        count++;
      } else {
        reqNoList.put(key, i);
      }
      i++;
    }
  }
}

I tried to do it in \$O(N)\$ but I have no idea.

Answer 1

The O(n²) approach

The first algorithm is indeed O(n²), because, for every element in the array, the array is traversed again to see whether an element after the current element is equal to 10 minus it. It is quite clear, and there is not much to change. Comments are:

• There is a bug: you're checking the same element twice in a row, since j, in the inner loop, starts at i. Therefore, if you consider the array { 1, 5, 2 }, the pair (5,5) will be considered a solution, when 5 only appeared once in the input array. To fix this, j should start at i + 1.

• Indent properly the code. As written, the curly braces are not aligned correctly, making it more difficult to read than it needs to be. A quick reformat by an IDE will produce

  int[] array = new int[] { 10, 3, 4, 6, 1, 9, 10, 0 };
  int sum = 0;
  
  for (int i = 0; i < array.length; i++) {
      for (int j = i; j < array.length; j++) {
          sum = array[i] + array[j];
          if (sum == 10) {
              System.out.println(array[i] + " " + array[j]);
          }
      }
  }
  

  which is easier to go through.

• There is no need to declare the sum variable outside the two for loops. This variable is only used inside to calculate the sum of two elements of the array. As a usual guideline, local variables should have the smallest possible scope, so in this case, you would prefer to have:

  int sum = array[i] + array[j];
  

  and remove the int sum = 0 before the loop.

The O(n) approach

The second algorithm is, as you say, O(n). The difference in approach with regard to the first, is that instead of traversing the array a second time for each element, we memorize along the way the difference between 10 and the current element. This means that we don't need to go through every element again, for each element, to check whether one satisfies; we can just continue and if we find one that we memorized, it means we just found a pair. A couple of comments again:

• There is a bug in the boundary of the while loop: why mandate i < sum? Because of this, not every element in the array will be considered (only the first sum ones), and pairs will be missed. A simple example is the array { 0, 1 } with a sum to search of 1. Once fixed, you can even turn this into a classic for loop, with an index going from 0 to nums.length excluded.
• Hashtable is considered an obsolete class. Not officially deprecated, but it has been superseded with faster solutions, like HashMap and ConcurrentHashMap. Since thread-safety is not a concern here, you can safely switch to HashMap.
• Remove the unused code. The variable count is declared, and incremented, but never used. In the same way, the variable temp is declared and never used.
• Notice how you're not using the value of the map. The code is doing reqNoList.put(key, i);, but then the stored i is never used. You could accomplish the same with a just HashSet instead of an HashMap.

They are not equivalent

But be careful, because there is a fundamental difference between the two algorithms, namely in how they handle duplicate pairs. Consider the array { 4, 4, 1, 0 }, and a sum to search of 5. The first algorithm will print two solutions, whereas the second one will just print one. So depending on what you want, there might be adjustements.

In you want to print them all using the second approach, you could do it by utilizing the value of the HashMap, and make it store the number of times a given element has been encountered.

---

As a final note, you should consider extracting each approach into their own method, like printPairsHavingSum(int[] array, int sum). It would clarify even more the code.