Complicated linked list issue

Question

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

Answer 1

I don't think this is possible in o(n²) (i.e. better than n² ), but it can be done in o(n²) (i.e. as n² ) as follows:

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

We can do this as follows (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) 

The uptime is O(n) . Extra O(1) space is required since we need to save only two pointers. Note that the above can easily be converted in such a way that it works with doubly linked lists.

Then, in general, 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 

This leads to runtime o(n²) and additional space O(1) .

Answer 2

Lists are sorted, right? Create a sorted array C 'from C to O (n) time.

For each of the n² x, y pairs in × B, check if - - (x + y) in C 'is a binary search. The total complexity of time is O (n² log n), the complexity of space is O (n).

Building a hash table from C leads to the complexity of time down to O (n²), due to the belief in O (1) hash tables.

Answer 3

You cannot do this with O (n) complexity, since this is an NP-complete problem (if only P = NP). Go to the Wiki page about Sumset Sum problem for possible solutions.