I have already given an O(n) solution. See above ! The BST solution is O(nlogn) but is practically more nice. :)
-------------------------------------------------- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Mon, Apr 12, 2010 at 1:16 PM, Nikhil Agarwal <nikhil.bhoja...@gmail.com>wrote: > > > On Mon, Apr 12, 2010 at 12:58 PM, Rohit Saraf <rohit.kumar.sa...@gmail.com > > wrote: > >> are yaar... i meant BST... i thought that was obvious ! >> sry if i confused you.... >> > > @rohit It's ok.Actually in this group people come up with very different > and non-common solutions so its risky to take things 'obviously'. > Rotation algo has a complexity of O(nlogn)[for constructing a BST] +O(n) > [for rotating n times]=O(nlogn) . > > Till now best algo we have is using heaps which give rise to complexity = > O(n+klogn) > > Please pass on algos having better runtime complexity. > >> >> >> -------------------------------------------------- >> Rohit Saraf >> Second Year Undergraduate, >> Dept. of Computer Science and Engineering >> IIT Bombay >> http://www.cse.iitb.ac.in/~rohitfeb14 >> >> >> On Mon, Apr 12, 2010 at 12:38 PM, Nikhil Agarwal < >> nikhil.bhoja...@gmail.com> wrote: >> >>> Hey rohit.You were referring to Binary tree.Search keyword was >>> missing.Because rotation makes no sense in binary tree.Please note binary >>> tree and BST are different. >>> >>> On Mon, Apr 12, 2010 at 12:33 PM, Rohit Saraf < >>> rohit.kumar.sa...@gmail.com> wrote: >>> >>>> Read the slides i uploaded. They explain what rotation does in a BST. >>>> >>>> Also you might like to refer to Red Black Trees in CLRS.... that chapter >>>> explains rotations. >>>> >>>> -------------------------------------------------- >>>> Rohit Saraf >>>> Second Year Undergraduate, >>>> Dept. of Computer Science and Engineering >>>> IIT Bombay >>>> http://www.cse.iitb.ac.in/~rohitfeb14 >>>> >>>> >>>> On Mon, Apr 12, 2010 at 8:18 AM, Rohit Saraf < >>>> rohit.kumar.sa...@gmail.com> wrote: >>>> >>>>> but still the binary tree solution is of more practical use.i will >>>>> explain the solution once i reach my comp >>>>> >>>>> >>>>> On 4/11/10, Nikhil Agarwal <nikhil.bhoja...@gmail.com> wrote: >>>>> > >>>>> > >>>>> > On Sun, Apr 11, 2010 at 9:56 PM, Rohit Saraf < >>>>> rohit.kumar.sa...@gmail.com> >>>>> > wrote: >>>>> >> >>>>> >> Time complexity is O(n log n). But the last solution I gave has >>>>> O(n). >>>>> >> >>>>> >> What did u not understand abt thesolution >>>>> > >>>>> > >>>>> > @Rohit Please explain how that Binary tree solution works. >>>>> >> >>>>> >> >>>>> >> -------------------------------------------------- >>>>> >> Rohit Saraf >>>>> >> Second Year Undergraduate, >>>>> >> Dept. of Computer Science and Engineering >>>>> >> IIT Bombay >>>>> >> http://www.cse.iitb.ac.in/~rohitfeb14 >>>>> >> >>>>> >> >>>>> >> On Sun, Apr 11, 2010 at 11:00 AM, Priyanka Chatterjee >>>>> >> <dona.1...@gmail.com> wrote: >>>>> >>> >>>>> >>> >>>>> >>> >>>>> >>> On 11 April 2010 10:46, Rohit Saraf <rohit.kumar.sa...@gmail.com> >>>>> wrote: >>>>> >>>> >>>>> >>>> Construct a binary tree from the data (maintain the size of >>>>> subtree >>>>> >>>> under each node). >>>>> >>>> Do rotations till the left subtree does not have size k. Rotation >>>>> is a >>>>> >>>> constant time operation. >>>>> >>>> Please prove the correctness of your algorithm with the time >>>>> complexity >>>>> >>>> >>>>> >>>> -------------------------------------------------- >>>>> >>>> Rohit Saraf >>>>> >>>> Second Year Undergraduate, >>>>> >>>> Dept. of Computer Science and Engineering >>>>> >>>> IIT Bombay >>>>> >>>> http://www.cse.iitb.ac.in/~rohitfeb14 >>>>> >>>> >>>>> >>>> >>>>> >>>> >>>>> >>>> On Mon, Mar 29, 2010 at 11:15 AM, blackDiamond < >>>>> patidarc...@gmail.com> >>>>> >>>> wrote: >>>>> >>>>> >>>>> >>>>> nice solution appreciate it. but your algorithm is wasting time >>>>> in >>>>> >>>>> finding all the element... >>>>> >>>>> instead of that just find boundary line kth element which can >>>>> help as >>>>> >>>>> in finding element greater that kth and element small than kth >>>>> and that >>>>> >>>>> soluton can be done in O(N) >>>>> >>>>> >>>>> >>>>> >>>>> >>>>> On Sun, Mar 28, 2010 at 10:02 PM, CHERUVU JAANU REDDY >>>>> >>>>> <jaanu.cher...@gmail.com> wrote: >>>>> >>>>>> >>>>> >>>>>> >>>>> >>>>>> 1) Construct max heap by taking first k elements in an array >>>>> >>>>>> 2) if k+1 element less than root of max heap >>>>> >>>>>> a) Delete root of max heap >>>>> >>>>>> b) Insert k+1 element in max heap and apply heapify >>>>> method >>>>> >>>>>> 3) else skip the element >>>>> >>>>>> 4) apply above procedure for all n elements in an array >>>>> >>>>>> >>>>> >>>>>> At last you will get k smallest elements and root is kth >>>>> smallest >>>>> >>>>>> element in the array >>>>> >>>>>> >>>>> >>>>>> this is O(nlogk) >>>>> >>>>>> >>>>> >>>>>> >>>>> >>>>>> >>>>> >>>>>> ---------------------------------------- >>>>> >>>>>> CHERUVU JAANU REDDY >>>>> >>>>>> M.Tech in CSIS >>>>> >>>>>> >>>>> >>>>>> >>>>> >>>>>> On Sun, Mar 28, 2010 at 8:41 PM, abhijith reddy >>>>> >>>>>> <abhijith200...@gmail.com> wrote: >>>>> >>>>>>> >>>>> >>>>>>> Can any one tell how to do this when there are 'm' queries like >>>>> >>>>>>> "query i j k" find the kth largest element in between indices >>>>> i->j in >>>>> >>>>>>> an array. >>>>> >>>>>>> When m is large even an O(n) algorithm would be slow. >>>>> >>>>>>> I thinking that each query could be answered in O(sqrt(n)) time >>>>> >>>>>>> So any suggestions ? >>>>> >>>>>>> >>>>> >>>>>>> Thanks >>>>> >>>>>>> >>>>> >>>>>>> >>>>> >>>>>>> On Sun, Mar 28, 2010 at 7:57 PM, blackDiamond < >>>>> patidarc...@gmail.com> >>>>> >>>>>>> wrote: >>>>> >>>>>>>> >>>>> >>>>>>>> there are better solution of O(n) are posted in the >>>>> thread.......[?]. >>>>> >>>>>>>> using order statices .... >>>>> >>>>>>>> >>>>> >>>>>>>> >>>>> >>>>>>>> On Sun, Mar 28, 2010 at 6:49 PM, Mukesh Kumar thakur >>>>> >>>>>>>> <mukeshraj8...@gmail.com> wrote: >>>>> >>>>>>>>> >>>>> >>>>>>>>> Create a temp array temp[0..k-1] of size k. >>>>> >>>>>>>>> 2) Traverse the array arr[k..n-1]. While traversing, keep >>>>> updating >>>>> >>>>>>>>> the smallest element of temp[] >>>>> >>>>>>>>> 3) Return the smallest of temp[] >>>>> >>>>>>>>> Time Complexity: O((n-k)*k). >>>>> >>>>>>>>> >>>>> >>>>>>>>> >>>>> >>>>>>>>> try it ..............for this problem[?] >>>>> >>>>>>>>> >>>>> >>>>>>>>> -- >>>>> >>>>>>>>> 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. >>>>> >>>>>>>>> To unsubscribe from this group, send email to >>>>> >>>>>>>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>>>> . >>>>> >>>>>>>>> For more options, visit this group at >>>>> >>>>>>>>> http://groups.google.com/group/algogeeks?hl=en. >>>>> >>>>>>>> >>>>> >>>>>>>> >>>>> >>>>>>>> >>>>> >>>>>>>> >>>>> >>>>>>>> -- >>>>> >>>>>>>> ~~~~BL/\CK_D!AMOND~~~~~~~~ >>>>> >>>>>>>> >>>>> >>>>>>>> -- >>>>> >>>>>>>> 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. >>>>> >>>>>>>> To unsubscribe from this group, send email to >>>>> >>>>>>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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. >>>>> >>>>>>> To unsubscribe from this group, send email to >>>>> >>>>>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algogeeks@googlegroups.com >>>>> . >>>>> >>>>>> To unsubscribe from this group, send email to >>>>> >>>>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>>>> . >>>>> >>>>>> For more options, visit this group at >>>>> >>>>>> http://groups.google.com/group/algogeeks?hl=en. >>>>> >>>>> >>>>> >>>>> >>>>> >>>>> >>>>> >>>>> >>>>> >>>>> -- >>>>> >>>>> ~~~~BL/\CK_D!AMOND~~~~~~~~ >>>>> >>>>> >>>>> >>>>> -- >>>>> >>>>> 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. >>>>> >>>>> To unsubscribe from this group, send email to >>>>> >>>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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. >>>>> >>>> To unsubscribe from this group, send email to >>>>> >>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>>>> . >>>>> >>>> For more options, visit this group at >>>>> >>>> http://groups.google.com/group/algogeeks?hl=en. >>>>> >>> >>>>> >>> >>>>> >>> >>>>> >>> >>>>> >>> -- >>>>> >>> Thanks & Regards, >>>>> >>> Priyanka Chatterjee >>>>> >>> Third Year Undergraduate Student, >>>>> >>> Computer Science & Engineering, >>>>> >>> National Institute Of Technology,Durgapur >>>>> >>> India >>>>> >>> http://priyanka-nit.blogspot.com/ >>>>> >>> >>>>> >>> -- >>>>> >>> 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. >>>>> >>> To unsubscribe from this group, send email to >>>>> >>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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. >>>>> >> To unsubscribe from this group, send email to >>>>> >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>>>> . >>>>> >> For more options, visit this group at >>>>> >> http://groups.google.com/group/algogeeks?hl=en. >>>>> > >>>>> > >>>>> > >>>>> > >>>>> > -- >>>>> > Thanks & Regards >>>>> > Nikhil Agarwal >>>>> > Junior Undergraduate >>>>> > Computer Science & Engineering, >>>>> > National Institute Of Technology, Durgapur,India >>>>> > http://tech-nikk.blogspot.com >>>>> > >>>>> > >>>>> > -- >>>>> > 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. >>>>> > To unsubscribe from this group, send email to >>>>> > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>>>> . >>>>> > For more options, visit this group at >>>>> > http://groups.google.com/group/algogeeks?hl=en. >>>>> > >>>>> >>>>> >>>>> -- >>>>> >>>>> -------------------------------------------------- >>>>> Rohit Saraf >>>>> Second Year Undergraduate, >>>>> Dept. of Computer Science and Engineering >>>>> IIT Bombay >>>>> http://www.cse.iitb.ac.in/~rohitfeb14 >>>>> >>>> >>>> -- >>>> 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. >>>> To unsubscribe from this group, send email to >>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>>> . >>>> For more options, visit this group at >>>> http://groups.google.com/group/algogeeks?hl=en. >>>> >>> >>> >>> >>> -- >>> Thanks & Regards >>> Nikhil Agarwal >>> Junior Undergraduate >>> Computer Science & Engineering, >>> National Institute Of Technology, Durgapur,India >>> http://tech-nikk.blogspot.com >>> >>> >>> -- >>> 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. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > Thanks & Regards > Nikhil Agarwal > Junior Undergraduate > Computer Science & Engineering, > National Institute Of Technology, Durgapur,India > http://tech-nikk.blogspot.com > > > -- > 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. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
<<338.gif>>
<<361.gif>>
