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 <[email protected]> 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 <[email protected]>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 < >> [email protected]> 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 < >>> [email protected]> wrote: >>> >>>> yes >>>> >>>> >>>> On Mon, Aug 15, 2011 at 12:58 AM, aditi garg <[email protected] >>>> > 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 <[email protected]> wrote: >>>>> >>>>>> no it is 3*n only........ read it again >>>>>> >>>>>> >>>>>> On Mon, Aug 15, 2011 at 12:45 AM, Amir Aavani >>>>>> <[email protected]>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< >>>>>>>> [email protected]> wrote: >>>>>>>> >>>>>>>> sorry O(n^2) s the time complexity >>>>>>>>> >>>>>>>>> >>>>>>>>> On 14 August 2011 23:56, shady<[email protected]> 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< >>>>>>>>>> [email protected]> 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 [email protected]. >>>>>>>>>>> To unsubscribe from this group, send email to >>>>>>>>>>> algogeeks+unsubscribe@**googlegroups.com<algogeeks%[email protected]> >>>>>>>>>>> . >>>>>>>>>>> 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 [email protected]. >>>>>>>>>> To unsubscribe from this group, send email to >>>>>>>>>> algogeeks+unsubscribe@**googlegroups.com<algogeeks%[email protected]> >>>>>>>>>> . >>>>>>>>>> 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 [email protected]. >>>>>>>>> To unsubscribe from this group, send email to >>>>>>>>> algogeeks+unsubscribe@**googlegroups.com<algogeeks%[email protected]> >>>>>>>>> . >>>>>>>>> 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 [email protected]. >>>>>>> To unsubscribe from this group, send email to algogeeks+unsubscribe@ >>>>>>> **googlegroups.com <algogeeks%[email protected]>. >>>>>>> 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 [email protected]. >>>>>> To unsubscribe from this group, send email to >>>>>> [email protected]. >>>>>> 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 [email protected]. >>>>> To unsubscribe from this group, send email to >>>>> [email protected]. >>>>> 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 [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
