Yes, navin thats a good solution... ... we dont need to work on the whole array but of size k x k (k rows and k columsn only). Rest of the array we can simply ignore..
complexity of youngify is O(k) for every removing every element. we have to remove k-1 elements so complexity of whole operation is o(k*k). Refer this pdf: http://lyle.smu.edu/~saad/courses/cse3358/ps5/problemset5sol.pdf Regards Saurabh On Mon, May 21, 2012 at 10:00 AM, Navin.nitjsr <[email protected]>wrote: > We can consider the 2-d matrix as a heap(also called Young Tableau). > We just need to heapify(Youngify) it k-1 times,then the element at > 0,0 will be kth smallest element. > This means we need to remove the k-1 smallest elements from matrix and > still maintaining its Row-Col sorted property. > Youngify algo:- > 1:- put a sentinel value (i,e, INF) 0,0 > 2:- Now push it leftwards/downwards to maintain the initial property of > matrix > 3:- If at any point the current element is smaller than both its left and > down element, then STOP. > > This is an in-place operation. > We need to consider the sentinel value as highest value,not present in the > matrix. > It works.Although the matrix is being modified. > > > > On Monday, 10 October 2011 04:45:52 UTC+5:30, Ankur Garg wrote: >> >> Given a 2D matrix which is both row wise and column wise sorted. Propose >> an algorithm for finding the kth smallest element in it in least time >> complexity >> >> A General Max Heap can be used with k space and n+klogk complexity >> >> Any other solution or even a way by which we dont scan the whole matrix >> to find the solution ? >> >> I >> > > On Monday, 10 October 2011 04:45:52 UTC+5:30, Ankur Garg wrote: >> >> Given a 2D matrix which is both row wise and column wise sorted. Propose >> an algorithm for finding the kth smallest element in it in least time >> complexity >> >> A General Max Heap can be used with k space and n+klogk complexity >> >> Any other solution or even a way by which we dont scan the whole matrix >> to find the solution ? >> >> I >> > > On Monday, 10 October 2011 04:45:52 UTC+5:30, Ankur Garg wrote: >> >> Given a 2D matrix which is both row wise and column wise sorted. Propose >> an algorithm for finding the kth smallest element in it in least time >> complexity >> >> A General Max Heap can be used with k space and n+klogk complexity >> >> Any other solution or even a way by which we dont scan the whole matrix >> to find the solution ? >> >> I >> > > On Monday, 10 October 2011 04:45:52 UTC+5:30, Ankur Garg wrote: >> >> Given a 2D matrix which is both row wise and column wise sorted. Propose >> an algorithm for finding the kth smallest element in it in least time >> complexity >> >> A General Max Heap can be used with k space and n+klogk complexity >> >> Any other solution or even a way by which we dont scan the whole matrix >> to find the solution ? >> >> I >> > -- > 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/-/GtGv_vms-WQJ. > > 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.
