Optimize the algorithm suggested above

Question

zhong · Accepted Answer

First sort the array, it costs O(n log(n)). 
With sorted array, to find any 2 elements whose sum equal to S (S could be any number) cost linear time O(n). 
Then for any element in the array Xi, set S = -Xi, and remove Xi from the array. Then do the "2 elements sum to S" problem with the modified array with total cost of O(n). Then all the results plus Xi equal to zero. 

The total cost will be: sorting O(n log(n)). For each Xi: need O(n), and all Xi, O(n^2). 

Algorithm to find sum of 2 elements equal to S in linear time: 
(assume there are no two elements that are equal to each other)
int L = 0; int H = nElements-1; // last element of the array
while (L S)
    {
       H--;
    }
    else if (A[L] + A[H] == S)
    {
        output(L, H); 
        L ++;
    }
 }

Anonymous · Answer

A more complete discussion of this problem can be found here:
http://en.wikipedia.org/wiki/3SUM

Note to Anonymous: This problem is NOT the same as subset sum and is not NP-Complete. Subset sum asks for an *arbitrary* subset that sums to some target value that is part of the problem instance, this problem asks for a set of *three* elements whose sum is 0.

Anonymous · Answer

def solve(arr):
    '''
    solve the problem and return tuple of tree integers.
    returns False, False, False if solution does not exist
    '''
    arr.sort()
    for x in xrange(len(arr)-2):
        y = x + 1
        z = len(arr)-1
        while y  0:
                z -= 1
            elif sum <0:
                y += 1
            else:
                return arr[x], arr[y], arr[z]
    return False, False, False

Anonymous · Answer

I doubt that the above "optimized" solution works since this is a well known NP-complete problem: http://en.wikipedia.org/wiki/Subset_sum_problem

Meta

Meta interview question

Interview Answers

Followed companies

Job searches

Bowls

Want the inside scoop on your own company?