Re: [algogeeks] Re: Algo for Search in a 2D Matrix
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 navin.nit...@gmail.comwrote: We can consider the 2-d matrix as a heap(also called Young Tableau). We just need to heapify(Youngify) it k-1times,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 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.
[algogeeks] Re: Algo for Search in a 2D Matrix
We can consider the 2-d matrix as a heap(also called Young Tableau). We just need to heapify(Youngify) it k-1times,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 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.
Re: [algogeeks] Re: Algo for Search in a 2D Matrix
@ashish: ya m sorry.. i didnt read the quest properly, it was for any given
number..
On Fri, May 18, 2012 at 11:37 AM, Ashish Goel ashg...@gmail.com wrote:
Anika, what you are talking about is finding a specific element, not the
kth largest or smallest element, can you give a walk through with an
example in case i have understood you incorrectly
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, May 17, 2012 at 3:33 PM, Anika Jain anika.jai...@gmail.comwrote:
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 hprem...@gmail.com
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 ashg...@gmail.com 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 vikas.rastogi2...@gmail.comwrote:
@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 sunny816.i...@gmail.com 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
anshumishra6...@gmail.comwrote:
struct data
{
int row, col,
int val;
};
priority_queuedata 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 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.
--
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
Re: [algogeeks] Re: Algo for Search in a 2D Matrix
i could not understand the Order Analysis of the solution ..is it k*(lg
n)(lg m) or k*lg(mn)
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Sun, May 20, 2012 at 11:15 PM, Anika Jain anika.jai...@gmail.com wrote:
@ashish: ya m sorry.. i didnt read the quest properly, it was for any
given number..
On Fri, May 18, 2012 at 11:37 AM, Ashish Goel ashg...@gmail.com wrote:
Anika, what you are talking about is finding a specific element, not the
kth largest or smallest element, can you give a walk through with an
example in case i have understood you incorrectly
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, May 17, 2012 at 3:33 PM, Anika Jain anika.jai...@gmail.comwrote:
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
hprem...@gmail.com 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 ashg...@gmail.com 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
vikas.rastogi2...@gmail.comwrote:
@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 sunny816.i...@gmail.com 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
anshumishra6...@gmail.comwrote:
struct data
{
int row, col,
int val;
};
priority_queuedata 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 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
Re: [algogeeks] Re: Algo for Search in a 2D Matrix
Anika, what you are talking about is finding a specific element, not the
kth largest or smallest element, can you give a walk through with an
example in case i have understood you incorrectly
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, May 17, 2012 at 3:33 PM, Anika Jain anika.jai...@gmail.com wrote:
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
hprem...@gmail.comwrote:
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 ashg...@gmail.com 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 vikas.rastogi2...@gmail.comwrote:
@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 sunny816.i...@gmail.com 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
anshumishra6...@gmail.comwrote:
struct data
{
int row, col,
int val;
};
priority_queuedata 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 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.
--
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.
--
Regards
Anika Jain
--
You received this message because you are
Re: [algogeeks] Re: Algo for Search in a 2D Matrix
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 hprem...@gmail.comwrote:
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 ashg...@gmail.com 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 vikas.rastogi2...@gmail.comwrote:
@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 sunny816.i...@gmail.com 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
anshumishra6...@gmail.comwrote:
struct data
{
int row, col,
int val;
};
priority_queuedata 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 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.
--
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.
--
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 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.
Re: [algogeeks] Re: Algo for Search in a 2D Matrix
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 vikas.rastogi2...@gmail.com 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 sunny816.i...@gmail.com 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
anshumishra6...@gmail.comwrote:
struct data
{
int row, col,
int val;
};
priority_queuedata 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 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.
Re: [algogeeks] Re: Algo for Search in a 2D Matrix
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 ashg...@gmail.com 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 vikas.rastogi2...@gmail.comwrote:
@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 sunny816.i...@gmail.com 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
anshumishra6...@gmail.comwrote:
struct data
{
int row, col,
int val;
};
priority_queuedata 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 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.
--
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.
Re: [algogeeks] Re: Algo for Search in a 2D Matrix
If O(k*logk) solution is acceptable then it is very simple.
maintain a min heap.
push a[0][0],
i = 0;
while ( i k)
{
pop an element. --- O(log(i)) -- coz number of elements in heap is i;
push the two adjacent element that is one right and right below. ---
O(log(i));
i++;
}
last element popped will be answer.
size of heap at every iteration will increase by one coz we are inserting
two elements and removing one element at every iteration.
If anyone has doubt on correctness of this solution can ask.
--
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.
Re: [algogeeks] Re: Algo for Search in a 2D Matrix
push the two adjacent element that is one right and below -- 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.
Re: [algogeeks] Re: Algo for Search in a 2D Matrix
@Anshu pushing adjacent element will cause duplicate entries in the heap try the following example: 1 2 3 4 5 6 7 2 3 4 5 6 7 8 3 4 5 6 7 8 9 4 5 6 7 8 9 10 so we also need to maintain a data structure that can efficiently tell that which cell has been pushed into the heap already. On Thu, Oct 13, 2011 at 11:35 AM, anshu mishra anshumishra6...@gmail.comwrote: push the two adjacent element that is one right and below -- 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.
Re: [algogeeks] Re: Algo for Search in a 2D Matrix
struct data
{
int row, col,
int val;
};
priority_queuedata 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 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.
Re: [algogeeks] Re: Algo for Search in a 2D Matrix
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 anshumishra6...@gmail.comwrote:
struct data
{
int row, col,
int val;
};
priority_queuedata 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 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.
[algogeeks] Re: Algo for Search in a 2D Matrix
@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 sunny816.i...@gmail.com 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
anshumishra6...@gmail.comwrote:
struct data
{
int row, col,
int val;
};
priority_queuedata 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 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.
[algogeeks] Re: Algo for Search in a 2D Matrix
@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.
Re: [algogeeks] Re: Algo for Search in a 2D Matrix
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.
Re: [algogeeks] Re: Algo for Search in a 2D Matrix
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.comwrote:
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.comwrote:
@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
Re: [algogeeks] Re: Algo for Search in a 2D Matrix
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.
[algogeeks] Re: Algo for Search in a 2D Matrix
@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.
