Steps: 1. Find the kth element using order statistics - O(n) 2. In one pass over the array, get all the elems less than the kth element.
Let me know if this is not correct. On Mon, Apr 12, 2010 at 1:57 PM, Rohit Saraf <rohit.kumar.sa...@gmail.com>wrote: > 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<http://www.cse.iitb.ac.in/%7Erohitfeb14> > > > 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<http://www.cse.iitb.ac.in/%7Erohitfeb14> >>> >>> >>> 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<http://www.cse.iitb.ac.in/%7Erohitfeb14> >>>>> >>>>> >>>>> 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<http://www.cse.iitb.ac.in/%7Erohitfeb14> >>>>>> >> >>>>>> >> >>>>>> >> 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<http://www.cse.iitb.ac.in/%7Erohitfeb14> >>>>>> >>>> >>>>>> >>>> >>>>>> >>>> >>>>>> >>>> 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 >>>>>> 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 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. >>>>>> >>>> >>>>>> >>>> >>>>>> >>>> -- >>>>>> >>>> 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<http://www.cse.iitb.ac.in/%7Erohitfeb14> >>>>>> >>>>> >>>>> -- >>>>> 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<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>>
