I think O(klogk) is possible.
array1=A={a1,a2,...,},B=arrary2={b1,b2,..}
think about the 2-d grid generated by A,B ( all points (ai,bj)).
using a swap line x+y=c, swap these point until we have scaned k point.
maintain a heap to tell which point will be the next point we will
scan.Moreover, if we can achieve o(klogk) is still open. since it reduce to the famous A+B problem when k=n^2. ref: http://maven.smith.edu/~orourke/TOPP/P41.html --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
