Sum of 2 numbers in an array [closed]

Question

I have this problem to solve:

Given an integer \$z\$ and an array \$a\$ of distinct integers sorted in ascending order, find two numbers, \$x\$ and \$y\$, belonging to the array such that \$x + y = z\$. All this has to be done with \$O(n)\$ time performance in the worst case and \$O(1)\$ space.

I tried to jot down a trivial solution:

public static boolean find(int[] a, int z) {
    for (int i = 0; i < a.length; i++) {
        for (int j = i + 1; j < a.length; j++) {
            if (a[i] + a[j] == z)
                return true;
        }
    }
    return false;
}

However, it is clearly O(n^2) and I cannot find a better algorithm. Can you help me?

Answer 1

Since there's no real review to do and we're apparently just posting solutions... here's a simple O(n) time O(1) space one:

public static boolean find(int[] a, int z) {
    int i = 0, j = a.length - 1;
    while (i < j) {
        int sum = a[i] + a[j];
        if (sum == z)
            return true;
        if (sum < z) i++; else j--;
    }
    return false;
}

Explanation: Try the ends, i.e., add the smallest and largest value. If the sum is right, bingo. If the sum is too small, then the smallest value is useless (it would need to be added with a number larger than the largest). If the sum is too large, then the largest value is useless. So remove the useless one. But since actually removing it, i.e., creating an array without it, would be expensive, just work with indexes marking the ends of the still potentially useful part of the array.

Answer 2

You can do this by "squeezing" the array. Suppose you had these inputs::

$$a = \{1, 4, 6, 9, 13, 16\}$$ $$z = 14$$

Obviously, the correct solution is \$(1, 13)\$. We can achieve this by taking the first value (it works fine in reverse as well), and stepping backwards through the array until we hit one of the following conditions:

1. You find the value we're looking for (\$a_{0} + a_{i} = z\$)
2. We reach a range that can never equal \$z\$ with \$a_{0}\$ (e.g. \$i = 3, 1 + 9 = 10 < 14\$)
3. We run into our current index (\$0\$).

In scenario #1, return true. In scenario #2, start squeezing from the left-side using the same rules. In scenario #3, return false.

A quickly jotted down implementation in Python - I am quite confident that you can simplify/condense this if you take a few more minutes to do this.

def squeeze_search(array, target):
    left_index = 0
    right_index = len(array) - 1

    while True:
        right_result = squeeze_right(array, target, left_index, right_index)
        if right_result is not None:
            success, left_index, right_index = right_result
            if success:
                return True
        else:
            return False
        left_result = squeeze_left(array, target, left_index, right_index)
        if left_result is not None:
            success, right_index, left_index = left_result
            if success:
                return True
        else:
            return False


def squeeze_left(array, target, current_index, left_index):
    current_value = array[current_index]
    while left_index < current_index:
        left_value = array[left_index]
        if left_value + current_value == target:
            return (True, current_index, left_index)
        elif left_value + current_value > target:
            return (False, current_index, left_index)

        left_index = left_index + 1

    return None

def squeeze_right(array, target, current_index, right_index):
    current_value = array[current_index]
    while right_index > current_index:
        right_value = array[right_index]
        if right_value + current_value == target:
            return (True, current_index, right_index)
        elif right_value + current_value < target:
            return (False, current_index, right_index)

        right_index = right_index - 1
    return None