For the second question have a stack as usual, but have a pointer for each stack entry. Have a head pointer which points to the minimum. These pointers point in the sorted order. This is explained by the following example. Suppose the elements are pushed in the following order : 3,6,1,8,2. Then the stack will look like : 2 8 1 6 3
The head points to 1. The pointer of 1 points to the next greater element i.e. 2. Similarly, the pointer of 2 points to 3 and so on. Clearly getMinElement() -------- O(1) push()------------------------------------O(n) in worst case pop()-------------------------------------O(n) in worst case When we push or we have to update the the pointers to account for the change in the sorted list.... I hope its clear. Feel free to comment. On Tue, Jun 28, 2011 at 7:15 AM, ankit sambyal <[email protected]> wrote: > @Shachindra: The second part of my solution can definitely be done in > O(n) time . Take 2 pointers : one pointing to the start of the array > and the second pointing to the end of the array. If sum of these 2 is > less than the required sum, increment the first pointer else increment > the second pointer .Iterate till u get the sum. > I hope its clear now. The same has been pointed out by Sunny. > > > > On Tue, Jun 28, 2011 at 6:29 AM, sunny agrawal <[email protected]> > wrote: >> 2nd part of ankit's solution can be easily done in O(n) >> after sorting of array >> >> i = 0, j = n-1 >> while(i < j) >> if a[i]+a[j] == x , i and j are indexes of the elements >> if a[i]+a[j] > x decrement j >> if a[i]+a[j] < x increment i >> >> >> On Tue, Jun 28, 2011 at 6:49 PM, Shachindra A C <[email protected]> >> wrote: >>> >>> @sagar : oops ! No need of sorting. Thank you for pointing out :) >>> >>> On Tue, Jun 28, 2011 at 6:41 PM, sagar pareek <[email protected]> >>> wrote: >>>> >>>> @Shachindra >>>> If you are using binary tree then why are you doing sorting first? >>>> >>>> @ANKIT >>>> Yes you can't do searching of sum of two numbers in less then O(n*n). >>>> >>>> On Tue, Jun 28, 2011 at 6:23 PM, Shachindra A C <[email protected]> >>>> wrote: >>>>> >>>>> @ankit : I'm pretty confident that the second part of your solution >>>>> cannot be done in O(n) time. Correct me if I am wrong!! Nevertheless, the >>>>> overall time complexity remains O(n*log(n)), as you pointed out. >>>>> >>>>> On Tue, Jun 28, 2011 at 5:59 PM, Shachindra A C <[email protected]> >>>>> wrote: >>>>>> >>>>>> @Ankit >>>>>> Can you please explain the method to get the answer to the second >>>>>> subpart of your solution in O(n) time? >>>>>> My solution to solve the problem in O(n log(n)) time is as follows: >>>>>> Insert the nodes of the sorted array into a binary tree. Then start >>>>>> with the first node. Subtract the value of the node from X. Then search >>>>>> for >>>>>> the result of the subtraction in the binary tree. This can be done in >>>>>> O(log >>>>>> n) time, giving O(nlogn) for the overall complexity of the second >>>>>> subproblem. >>>>>> Please explain your logic. >>>>>> >>>>>> On Tue, Jun 28, 2011 at 5:48 PM, Nitish Garg <[email protected]> >>>>>> wrote: >>>>>>> >>>>>>> Can you please explain how to solve the 2nd question? >>>>>>> >>>>>>> -- >>>>>>> You received this message because you are subscribed to the Google >>>>>>> Groups "Algorithm Geeks" group. >>>>>>> To view this discussion on the web visit >>>>>>> https://groups.google.com/d/msg/algogeeks/-/5C-1NnideVgJ. >>>>>>> To post to this group, send email to [email protected]. >>>>>>> To unsubscribe from this group, send email to >>>>>>> [email protected]. >>>>>>> For more options, visit this group at >>>>>>> http://groups.google.com/group/algogeeks?hl=en. >>>>>> >>>>>> >>>>>> >>>>>> -- >>>>>> Regards, >>>>>> Shachindra A C >>>>> >>>>> >>>>> >>>>> -- >>>>> Regards, >>>>> Shachindra A C >>>>> >>>>> -- >>>>> You received this message because you are subscribed to the Google >>>>> Groups "Algorithm Geeks" group. >>>>> To post to this group, send email to [email protected]. >>>>> To unsubscribe from this group, send email to >>>>> [email protected]. >>>>> For more options, visit this group at >>>>> http://groups.google.com/group/algogeeks?hl=en. >>>> >>>> >>>> >>>> -- >>>> Regards >>>> SAGAR PAREEK >>>> COMPUTER SCIENCE AND ENGINEERING >>>> NIT ALLAHABAD >>>> >>>> -- >>>> You received this message because you are subscribed to the Google Groups >>>> "Algorithm Geeks" group. >>>> To post to this group, send email to [email protected]. >>>> To unsubscribe from this group, send email to >>>> [email protected]. >>>> For more options, visit this group at >>>> http://groups.google.com/group/algogeeks?hl=en. >>> >>> >>> >>> -- >>> Regards, >>> Shachindra A C >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >> >> >> >> -- >> Sunny Aggrawal >> B-Tech IV year,CSI >> Indian Institute Of Technology,Roorkee >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
