there's a solution of O(log n) where 2D matrix has n rows and n columns. Apply binary search for the search on the diagonal. when you are left with just one element after the search apply binary search within that elements row and its column. you will get the element. O(log n+log n+log n). so O(log n).
On Wed, May 16, 2012 at 6:36 PM, Prem Krishna Chettri <[email protected]>wrote: > Well I hv got Something running in my mind buy ofcse need some cornor case > tuning. > > If we take sqrt() of the number (say K) than we can avoid looking into > sqrt(k)-1 and sqrt(k)+1 rows and column entirely, which literally means > that the final solution is possible in constant time (the time independent > of k or matrix values), which ofcourse can go upto O(n) in worst case where > N is the Matrix of N Rows and 1 Column as we cannot use the intelligence of > sqrt function to corner the value. > > Its seems okei logically to remove those rows and columns as we are > certain that they are sorted in both ways and avoid unnecessary time > looking for the place where it won't belong. > > Now the issue is so clear that we can say (sqrt(k)-1)*(sqrt(k)-1)<k and > now keep on adding the value to sqrt(k)+1 till U reach k and get corner > that element. > > I guess it works.. > > > > On Wed, May 16, 2012 at 1:17 PM, Ashish Goel <[email protected]> wrote: > >> Vikas, can you suggest the logic of this also? I am a bit unclear on how >> the 2D arr is being used as a heap and how recursion is used to solve this >> >> Best Regards >> Ashish Goel >> "Think positive and find fuel in failure" >> +919985813081 >> +919966006652 >> >> >> >> On Thu, Oct 13, 2011 at 11:37 PM, vikas <[email protected]>wrote: >> >>> @Sunny, good catch, k X k approach wont work >>> >>> lets try to use matrix itself as heap >>> >>> heapify(int cr, int cc, int Nr, int Nc){ >>> mr = cr; mc = cc; >>> if(cr+1 < Nr) >>> mr = cr+1 mc = cc; >>> if(cc + 1 < Nc && min > A[cc+1][cr]) >>> mr = cr; mc = cc+1; >>> if(A[cr][cc] > A[mr][mc]){ >>> swap(&A[cr][cc] ,&A[mr][mc]); >>> heapify(mr, mc, Nr, Nc); >>> } >>> >>> extract_min(){ >>> swap(&A[0][0], &A[hr][hc]); >>> if(hc > 0) hc--; >>> else if(hr > 0){ >>> hr --; >>> hc = N; >>> } >>> if(hr | hc) >>> heapify(0, 0, hr, hc); >>> } >>> >>> >>> } >>> >>> >>> On Oct 13, 12:18 pm, sunny agrawal <[email protected]> wrote: >>> > Nopes >>> > Still it does not ensure that duplicates will not be there in the >>> priority >>> > queue >>> > >>> > what i mean is you cannot write directly >>> > >>> > do k times{ >>> > data = pop() >>> > // let i,j are row and col of data >>> > push(i+1,j); >>> > push(i,j+1); >>> > >>> > } >>> > >>> > you need to add the following checks >>> > >>> > if((i+1,j) is not in the heap) push(i+1,j) >>> > if((i,j+1) is not in the heap) push(i,j+1) >>> > because heap does not automatically check for duplicates >>> > >>> > and to check for duplicates we need an extra data structure other than >>> heap, >>> > which stores that which (i+1,j) are already there in the heap map can >>> also >>> > be used so overall complexity will go O(k* lg^2K) >>> > >>> > On Thu, Oct 13, 2011 at 12:26 PM, anshu mishra < >>> [email protected]>wrote: >>> > >>> > >>> > >>> > > struct data >>> > > { >>> > > int row, col, >>> > > int val; >>> > > }; >>> > >>> > > priority_queue<data> heap; >>> > >>> > > now fine? >>> > >>> > > -- >>> > > 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. V 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. >> > > -- > 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 Anika Jain -- 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.
