tricky linked list problem

Question

Given three lists: A, B and C of length n each. if any 3 three numbers (1 from each list), sum up to zero return true.I want to solve this with o(n)complexity.I have sorted the lists and I can think of creating either a hash map with sum of 2 linked lists or comparing 3 lists together[o(n*n*n)].Suggest some ways to improvise the methods to reduce complexity..I can't think of any...Thanks in adv

Answer 1

The lists are sorted, right? Build a sorted array C' out of C in O(n) time.

For each of the n² pairs x, y in A × B, check if -(x + y) is in C' with binary search. Total time complexity is O(n² lg n), space complexity is O(n).

Building a hash table out of C brings the time complexity down further to O(n²), at the expense of belief in O(1) hash tables.

Answer 2

I do not think it is possible in o(n²) (i.e. really better than n²), but it can be done in O(n²) (i.e. sth. like n²) as follows:

First of all, reverse list B to obtain B' (takes O(n) time), a list whose items are sorted in descending order. First, we consider the problem of finding two elements in the lists A and B' that sum to any given number:

We can do this like the following (Python code):

def getIndicesFromTwoArrays(A,B,t):
    a,b=0,0
    while(A[a]+B[b]!=t):
        b=b+1
        if b==len(B):
            return (-1,-1)
        if A[a]+B[b]<t:
            a=a+1
            b=b-1
            if a==len(A):
                return (-1,-1)
    return (a,b)

Run time of the above is O(n). Additional space required is O(1) since we only have to store two pointers. Note that the above can be easily transformed such that it works with doubly linked lists.

Then, overall we just have to do the following:

def test(A,B,C):
    B.reverse()
    for c in C:
        if getIndicesFromTwoArrays(A, B, c) != (-1,-1):
            return True
    return False

That results in running time O(n²) and additional space O(1).