@shady : what if all the rows hai one min and one max element , which is
re occurring. your algo doesn't check that
On Mon, Aug 15, 2011 at 1:37 AM, aditya kumar
<aditya.kumar130...@gmail.com>wrote:
> @all: it will take O(3n) for finding max n min and if and only if all
> elements in an array are distinct .
>
> On Mon, Aug 15, 2011 at 1:30 AM, siddharth srivastava <akssps...@gmail.com
> > wrote:
>
>>
>> One approach could be:
>>
>> I think the min and max elements can be found in n*n*(3n/2)
>> keep a flag(or array of flag--bitvector ??) for the rows in which min or
>> max was found
>> print all other rows for which flag is not set
>>
>> another n^3(confirm please) algo could be:
>> sort each row individually
>> compare first col for min, last col for max
>> print all which do not have min or max
>>
>>
>>
>>
>> On 15 August 2011 01:20, shady <sinv...@gmail.com> wrote:
>>
>>> according to me it would be take 4*n time.... 3 iterations to choose the
>>> min. and max. from 1st three rows, and n again to print the chosen one
>>>
>>>
>>> On Mon, Aug 15, 2011 at 1:13 AM, aditi garg
>>> <aditi.garg.6...@gmail.com>wrote:
>>>
>>>> some how im not able to get the logic...how will i be able to find max
>>>> and min of the entire matrix by jst traversing 3 rows??
>>>>
>>>> for eg
>>>> 1 2 3 4 5
>>>> 8 1 3 6 9
>>>> 4 6 3 2 10
>>>> 9 0 5 8 12
>>>> 18 2 6 7 3
>>>> fr dis matrix how will u find max and min??
>>>>
>>>>
>>>> On Mon, Aug 15, 2011 at 1:04 AM, aditya kumar <
>>>> aditya.kumar130...@gmail.com> wrote:
>>>>
>>>>> just traverse the three rows and get the max and min out of the three
>>>>> rows . print the row in which their is no max and min .
>>>>>
>>>>>
>>>>> On Mon, Aug 15, 2011 at 1:02 AM, aditya kumar <
>>>>> aditya.kumar130...@gmail.com> wrote:
>>>>>
>>>>>> yes
>>>>>>
>>>>>>
>>>>>> On Mon, Aug 15, 2011 at 12:58 AM, aditi garg <
>>>>>> aditi.garg.6...@gmail.com> wrote:
>>>>>>
>>>>>>> @shady : does O(3n) include the time required to find the max and min
>>>>>>> element as well??
>>>>>>>
>>>>>>>
>>>>>>> On Mon, Aug 15, 2011 at 12:50 AM, shady <sinv...@gmail.com> wrote:
>>>>>>>
>>>>>>>> no it is 3*n only........ read it again
>>>>>>>>
>>>>>>>>
>>>>>>>> On Mon, Aug 15, 2011 at 12:45 AM, Amir Aavani <
>>>>>>>> amir.aav...@gmail.com> wrote:
>>>>>>>>
>>>>>>>>>
>>>>>>>>> On 08/14/2011 11:46 AM, aditya kumar wrote:
>>>>>>>>>
>>>>>>>>>> it can be done in O(3n). in worst case one row will have max and
>>>>>>>>>> anothr row
>>>>>>>>>> will have min so the third row will be your o/p to print
>>>>>>>>>>
>>>>>>>>> Do you mean O(n^3)?
>>>>>>>>>
>>>>>>>>> Consider this { O(n^2) }:
>>>>>>>>>
>>>>>>>>> 1- Scan the whole matrix and find minimum and maximum entries in
>>>>>>>>> the matrix. Let Delta be the difference between maximum and minimum.
>>>>>>>>> 2- For each row, find the minimum and maximum entries in that row.
>>>>>>>>> If their difference is exactly Delta, then print that row.
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> Amir
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>> On Mon, Aug 15, 2011 at 12:00 AM, Karthikeyan palani<
>>>>>>>>>> karthikeyan...@gmail.com> wrote:
>>>>>>>>>>
>>>>>>>>>> sorry O(n^2) s the time complexity
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> On 14 August 2011 23:56, shady<sinv...@gmail.com> wrote:
>>>>>>>>>>>
>>>>>>>>>>> how can it be O(n) when there are itself n*n elements..
>>>>>>>>>>>>
>>>>>>>>>>>> PS : no sharing of code, else the inevitable
>>>>>>>>>>>>
>>>>>>>>>>>> On Sun, Aug 14, 2011 at 11:51 PM, Karthikeyan palani<
>>>>>>>>>>>> karthikeyan...@gmail.com> wrote:
>>>>>>>>>>>>
>>>>>>>>>>>> Given a n x n matrix. .number are randomly placed. .print any
>>>>>>>>>>>>> one row
>>>>>>>>>>>>> which doesn’t have min
>>>>>>>>>>>>> and max elements. Time Complexity : 0(n)
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> if anyone know the code.. pls share!!!
>>>>>>>>>>>>>
>>>>>>>>>>>>> --
>>>>>>>>>>>>> karthikeyankkn
>>>>>>>>>>>>>
>>>>>>>>>>>>> --
>>>>>>>>>>>>> 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+unsubscribe@**googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>>>>>>>>>>>>> .
>>>>>>>>>>>>> For more options, visit this group at
>>>>>>>>>>>>> http://groups.google.com/**group/algogeeks?hl=en<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+unsubscribe@**googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>>>>>>>>>>>> .
>>>>>>>>>>>> For more options, visit this group at
>>>>>>>>>>>> http://groups.google.com/**group/algogeeks?hl=en<http://groups.google.com/group/algogeeks?hl=en>
>>>>>>>>>>>> .
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> --
>>>>>>>>>>> karthikeyankkn
>>>>>>>>>>>
>>>>>>>>>>> --
>>>>>>>>>>> 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+unsubscribe@**googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>>>>>>>>>>> .
>>>>>>>>>>> For more options, visit this group at
>>>>>>>>>>> http://groups.google.com/**group/algogeeks?hl=en<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+unsubscribe@**googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>>>>>>>>> .
>>>>>>>>> For more options, visit this group at http://groups.google.com/**
>>>>>>>>> group/algogeeks?hl=en<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.
>>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> --
>>>>>>> Aditi Garg
>>>>>>> Undergraduate Student
>>>>>>> Electronics & Communication Divison
>>>>>>> NETAJI SUBHAS INSTITUTE OF TECHNOLOGY
>>>>>>> Sector 3, Dwarka
>>>>>>> New Delhi
>>>>>>>
>>>>>>>
>>>>>>> --
>>>>>>> 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.
>>>>>
>>>>
>>>>
>>>>
>>>> --
>>>> Aditi Garg
>>>> Undergraduate Student
>>>> Electronics & Communication Divison
>>>> NETAJI SUBHAS INSTITUTE OF TECHNOLOGY
>>>> Sector 3, Dwarka
>>>> New Delhi
>>>>
>>>>
>>>> --
>>>> 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
>> Siddharth Srivastava
>>
>>
>> --
>> 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.
>
--
Ankur Khurana
Computer Science
Netaji Subhas Institute Of Technology
Delhi.
--
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.
