@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.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.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.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.com>wrote:
>>>>> >
>>>>> >
>>>>> >
>>>>> > > struct data
>>>>> > > {
>>>>> > > int row, col,
>>>>> > > int val;
>>>>> > > };
>>>>> >
>>>>> > > priority_queue<data> 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.
>>
>
> --
> 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.
