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.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.
>
--
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.
