0
\$\begingroup\$

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?

\$\endgroup\$
2
  • 1
    \$\begingroup\$ looks like a problem from LeetCode \$\endgroup\$ Sep 1 '20 at 20:34
  • 2
    \$\begingroup\$ When the problem statement clearly states \$O(n)\$ time and your solution is \$O(n^2)\$ I can only close-vote as "not implemented / not working as intended". You are not looking for a review, you are looking for a solution you have not found. \$\endgroup\$
    – mtj
    Sep 2 '20 at 10:49
7
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ You have presented an alternative solution, but haven't reviewed the code. Please explain your reasoning (why it is better than the original) so that the author and other readers can learn from your thought process. \$\endgroup\$
    – Mast
    Sep 2 '20 at 7:12
  • \$\begingroup\$ @Mast Done that. \$\endgroup\$ Sep 2 '20 at 9:09
  • \$\begingroup\$ You're fairly new on CR, the point @Mast might have really been trying to make is that the question is off topic, therefore it shouldn't be answered. For stack overflow this would probably be a great answer. \$\endgroup\$
    – pacmaninbw
    Sep 2 '20 at 11:03
  • 2
    \$\begingroup\$ @pacmaninbw I thought/think it's off-topic, too, see my first sentence. But then Dannnno (who has been here longer than even you, and has fairly high reputation) posted their answer, and someone upvoted it. So I figured I'd do it as well. Partially because their solution is so horrifically complicated. \$\endgroup\$ Sep 2 '20 at 11:09
  • 1
    \$\begingroup\$ Agreed, Dannnno should have known better and you did post a better solution. \$\endgroup\$
    – pacmaninbw
    Sep 2 '20 at 11:13
2
\$\begingroup\$

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
\$\endgroup\$
0

Not the answer you're looking for? Browse other questions tagged or ask your own question.