im assuming it be a square matrix
then kth smallest element will be in a first k*k sub matrix.
jst look for smallest element in the diagonal of this matrix.
it will give the kth smallest element .
On Mon, Oct 10, 2011 at 4:45 AM, 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 post to this group, send email to algogeeks@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.
>
--
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.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.