Determine a list contains two elements with a given sum

Question

On interview I was asked to write method with following contract:

boolean checkList(List<Long> list, long sum){...}

for example it has to return true for arguments:
({1,2,3,4,5,6}, 9) because 4+5 = 9

and it have to return false for arguments:

({0,10,30}, 11) because there are no combination of 2 elements with sum 11

I suggested code like this:

boolean checkList(List<Long> list, long expectedSum) {
    if (list.size() < 2) {
        return false;
    }
    for (int i = 0; i < list.size() - 1; i++) {
        for (int k = i; k < list.size(); k++) {
            if ((list.get(i) + list.get(k)) == expectedSum) {
                return true;
            }
        }
    }
    return false;
}

But interviewer asked me to improve the solution. How?

Answer 1

As 200_success mentions, your solution is \$O(n^2)\$, due to the double for loop.

You actually have an error in your inner loop. You start the inner loop with for (int k = i; ..., but it should be for (int k = i + 1; .... This means you could return true for an even expected sum when half of that value appears once in the list.

If you correct the above error, the test for list.size() < 2 is unnecessary. The outer loop will run at most once (size=1) and the inner loop will not run at all, therefore the return false; at the end of the function will be executed.

---

An \$O(n)\$ solution is:

• start with an empty set
• for each value x in the list:
  • if set contains expectedSum - x, return true
  • add x to the set.
• returnfalse

It is important to check for containment before adding the value, or ({1,2,3,4}, 8) would return true, despite not containing a pair of 4’s.

Set<Long> set = new HashSet<>(list.size()*2);
for(long x: list) {
    if (set.contains(expectedSum - x)) {
        return true;
    }
    set.add(x);
}
return false;

The list does not need to be sorted.

The capacity of the HashSet is initialized to double the size of the list, to avoid re-sizings, which would slow the algorithm down.

From the comments: "Why double?" The default load factor for a HashSet is 0.75. If the number of elements in the set exceeds load_factor * capacity, the capacity is increased and the contents rehashed for the new size. If the capacity was set to the size of the list, it would still end up expanding the capacity and rehashing after adding the first 75% of the entries in the list. You need an initial capacity at least 33% larger than the final size to avoid the expansion: list.size()*4/3 + 1 might be sufficient, but is perhaps cutting things a little too fine. Double seemed a reasonable amount.

Answer 2

There are many ways to solve this puzzle. Your approach seems to fine. It is simple and it is easy to understand. But you can replace your inner loop by a method of List:

public static boolean checkList_contains(List<Integer> list, int sum) {
    if (list.size() < 2) {
        return false;
    }
    for (int i = 0; i < list.size() - 1; i++) {
        if (list.contains(sum - list.get(i)))
            return true;
    }
    return false;
}

This tries to find the missing value by calling contains.

Then you can use modern streams instead of for loops:

public static boolean checkList_streams(List<Integer> list, int sum) {
    return list.stream()
            .map(x -> sum - x)
            .filter(list::contains)
            .findAny()
            .isPresent();
}

But here it should be allowed to use the same element twice.

Theses both solutions are very inefficient. Both have a running time in O(n²).

If you expect a sorted list you can use two indices which moves from left and right until you find a matching pair (which is what @200_success has written):

public static boolean checkList_sorted_list(List<Integer> list, int sum) {
    int lowerIndex = 0;
    int upperIndex = list.size() - 1;
    while (lowerIndex < upperIndex) {
        int testSum = list.get(lowerIndex) + list.get(upperIndex);
        if (testSum > sum) upperIndex --;
        else if (testSum < sum) lowerIndex ++;
        else return true;
    }
    return false;
}

This is in O(n).

Answer 3

Your solution is inefficient: for a list of length n, the worst-case running time is O(n²), because you may need to test every possible pair of numbers.

A better algorithm would be to sort the list first. (Maybe it's already sorted? You didn't specify, but your examples suggest that that might be the case.) Then, you would only need to try pairs where the left index only increases (if the pair sum is too small) and the right index only decreases (if the pair sum is too large). The running time for that would be O(n log n) for the sorting step, plus O(n) for the search.