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.
