it will work only if all numbers are unique On Mon, Aug 15, 2011 at 10:50 AM, Ankur Khurana <[email protected]>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 < > [email protected]> 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 < >> [email protected]> 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 <[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. >>> >> >> -- >> 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. >> > > > > -- > 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 [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.
