It is clearly O(n^2) . However i am sure there must be better methods available then this semi-naive method. Once i saw a problem which was on 4 lists and not three like here. So same algorithm on that case delievers O(n^3) and was giving me TLE. So yes , we should be able to do it nlogn somehow.
On Sun, Nov 1, 2009 at 2:20 PM, Arun <arunm...@gmail.com> wrote: > sorry it has to be k=k+1 in "k=k-1 goto AGAIN" as C is descending order. > > > On Sun, Nov 1, 2009 at 1:48 AM, Arun <arunm...@gmail.com> wrote: > >> I think daizi sheng is right, its O(n^2) >> if i rewrite his algo slgihtly, which makes me more clear >> A,B -> sorted in ascending >> C in descending >> foreach(ai in A) >> ck = largest element in C >> j=1 >> >> AGAIN: >> if(ai + bj + ck == 0) algorithm over >> if(ai + bj + ck > 0) k=k-1 goto AGAIN >> if(ai + bj + ck < 0) j=j+1 >> >> On Sun, Nov 1, 2009 at 1:28 AM, anilkumarmyla >> <anilkumarm...@gmail.com>wrote: >> >>> That way your solution takes more than O(N^2), because of the AGAIN loop. >>> >>> >>> On Sun, Nov 1, 2009 at 1:09 PM, daizi sheng <daizish...@gmail.com>wrote: >>> >>>> with all arrays sorted firstly, if you enumerate ai, bj in ascedning >>>> order, >>>> ck will be sure in descending order. >>>> >>>> foreach(ai in A) >>>> ck = largest element in C >>>> foreach(bj in B) >>>> AGAIN: >>>> if(ai + bj + ck == 0) algorithm over >>>> if(ai + bj + ck > 0) ck change to its neighbor in C and goto AGAIN >>>> if(ai + bj + ck < 0) continue checking next bj >>>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to algoge...@googlegroups.com. >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- nikhil- -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
