Is using ArrayList.contains() inside a for loop actually more efficient than using nested loops to compare?

Question

I have been doing some practice tech interview questions, and this one has been pretty easy, but I am wondering if the more efficient of my two solutions is actually so.

I now see that someone else on here has previously asked this question, but my question has the code snippets and I fell it may provide further insight for anyone else who is searching for a solution.

The question is: given an array of integers and some number k, create a function that returns true if any two numbers in the array add to k.

Here is my "slow" solution:

private static boolean canAddToKSlow(int[] nums, int k) {
    /*
    Uses double for loops to compare each value in the array to
    another value (not including the current one). If they add
    up to k, return true. Otherwise, at the end of iteration,
    return false.
    */

    for(int i = 0; i < nums.length; i++) {
      for(int j = 0; j < nums.length; j++) {
        if (j != i) {
          if (nums[i] + nums[j] == k) {
            return true;
          }
        }
      }
    }

    return false;
  }

and my "fast" solution:

private static boolean canAddToKFast(int[] nums, int k) {
    /*
    Uses a single optimized for loop to iterate through the list,
    and adds the "complement" of the current int to the arraylist.
    By complement, I mean whatever number you would have to add to
    n to get k. Then, it checks to see if that n is in the arraylist, and if so, then there must be two numbers that 
    add to k. More efficient.
    */
    ArrayList<Integer> comps = new ArrayList<>();

    for(int n: nums) {
      comps.add(k - n);
      if(comps.contains(n))
        return true;

    }

    return false;
 }

The problem that I am running into here is that ArrayList.contains() calls indexOf(), which uses for loops anyway, so it may be just as inefficient and just obfuscated. Is there any voodoo magic that makes the second solution any more efficient? If not, is there actually a way to make this more efficient or is this the best you can do? I wonder if a hash table would make any difference.

Answer 1

The efficiency is not different in both cases, because list.contains() has a time complexity of O(n), so both have a time complexity of O(n²).

A better solution would be to use HashSet.contains() which has a time complexity of O(1).

This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets. (docs)

So the time complexity of this is O(n):

private static boolean canAddToKFast2(int[] nums, int k) {
    Set<Integer> comps = new HashSet<>();
    for (int n : nums) {
        if (comps.contains(n))
            return true;
        comps.add(k - n);
    }
    return false;
}

Answer 2

Here is an O(n) solution using a hash table, but it does use extra space:

    private static boolean canAddToKFast2(int[] nums, int k) {

        Map<Integer,Integer> table = new HashMap<Integer, Integer>();

        for(int val: nums) {
            if(table.containsKey(k - val)) { // O(1) lookup to see if the difference exists
                return true;
            }
            table.put(val, val); //If it doesn't exist, add the value to the table
        }
        return false; // We searched all values and didn't find a pair
    }

This is O(n) time and we can see that because we only touch each element once. If the target minus element doesn't exist in the table, then we insert it into the table. If we loop through all the items and don't find a match, return false.

What about space efficiency?

With regards to your interview, I would ask if extra space is allowed (the hash table is going to use O(n) space). If extra space is not allowed, then the most efficient answer is the code in your question (which runs in O(n²) time and does not use any additional space.