Hey guys don't panic
original question have unique numbers
palani haven't read the question properly
hence it can be done in O(3n)
On Mon, Aug 15, 2011 at 11:28 AM, shady <sinv...@gmail.com> wrote:
> it will work only if all numbers are unique
>
>
> On Mon, Aug 15, 2011 at 10:50 AM, Ankur Khurana
> <ankur.kkhur...@gmail.com>wrote:
>
>> @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.
>>
>
> --
> 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
SAGAR PAREEK
COMPUTER SCIENCE AND ENGINEERING
NIT ALLAHABAD
--
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.
