Here is a solution based on the fact that the matrix is quiet similar to a
min heap. each cell is smaller than its down and right neighbor.
Note :- This solution modifies the original matrix.
Algo -
repeat k-1 times
set a[0][0] = INFINITY
minHeapify the Matrix (see implementation below). This will create
holes in the matrix that can be filled with INFINITY.
return a[0][0];
- Complexity O(k*(m+n)) for a m x n matrix.
- Here is a java implementation of the same.
public static int kthSmallest(int[][] a, int k)
{
final int INF = Integer.MAX_VALUE;
int rows = a.length;
int cols = a[0].length;
if (k > rows*cols)
{
System.out.println("Matrix has less than " + k + " elements.");
return INF;
}
while(--k > 0)
{
a[0][0] = INF; int i=0, j=0;
// MinHeapify the matrix again.
while(true)
{
int down = INF; int right = INF;
if(i < rows-1) down = a[i+1][j];
if(j < cols-1) right = a[i][j+1];
if((down == INF) &&(right == INF))
break;
if(down < right)
{
int temp = a[i][j];
a[i][j] = down;
a[i+1][j] = temp;
i++;
}
else
{
int temp = a[i][j];
a[i][j] = right;
a[i][j+1] = temp;
j++;
}
}
}
return a[0][0];
}
Feedback welcome :-)
- Ravindra
On Wed, Oct 12, 2011 at 8:18 PM, sunny agrawal <sunny816.i...@gmail.com>wrote:
> i dont think k*k submatrix approach works at all
> what if k >=n size of submatrix will be n*n, which is matrix itself
> heap seems to be a good approach with a coloring scheme that helps in
> avoiding duplicates in heap ??
>
>
> On Wed, Oct 12, 2011 at 7:18 PM, vikas <vikas.rastogi2...@gmail.com>wrote:
>
>> @Shiva, not necessarily in upper half
>>
>> take the transpose of example put by Dave and see by yourself
>>
>> There are few observations for this question:
>> 1. kth smallest will always lie in first k*k matrix
>> 2. it wont be part of sqrt(k)*sqrt(k) matrix
>> Thus rest all need to be searched recursively to find the element
>>
>> Any suggestions ?
>>
>>
>> On Oct 10, 10:55 am, "shiva@Algo" <shiv.jays...@gmail.com> wrote:
>> > id we see the pattern then we can easily find that the kth smallest
>> element
>> > lie on the upper half of the k*k submatrix(on the upperleft corner )
>> > we can do search on (k*k)/2 elements to find that
>> >
>> > On Mon, Oct 10, 2011 at 10:36 AM, Dave <dave_and_da...@juno.com> wrote:
>> > > @Shubham: So if the matrix is
>> > > 1 2
>> > > 3 4
>> > > and you want the 2nd smallest, are you saying that it is 4?
>> >
>> > > Dave
>> >
>> > > On Oct 9, 7:40 pm, shubham goyal <shubhamgoyal.n...@gmail.com> wrote:
>> > > > 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 <ankurga...@gmail.com>
>> > > 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.
>>
>> --
>> 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.
>>
>>
>
>
> --
> 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 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.
