@Anika: You don't have to find the max and min elements of the entire array to find a row that doesn't contain either of them. If you scan 3 rows, you will find a row that contains the max of those three rows, another that contains the min, and the remaining row will contain neither. Scanning the rest of the array would serve only to increase the maximum and decrease the minimum, but it wouldn't alter the fact that that remaining row doesn't contain either. Thus, we don't need to scan the rest of the matrix.
Dave On Aug 16, 11:23 pm, Anika Jain <[email protected]> wrote: > i didnt get it tht even if there are distinct elements how scanning sum > three lines return us the max n min elements? how will this scan whole > matrix for finding the max n min elements??? > > On Wed, Aug 17, 2011 at 1:32 AM, priya ramesh < > > > > [email protected]> wrote: > > are these algos optimal??? > > *Algo 1*: > > > no_min_max = -1 > > min_row = max_row = -1 > > for(i=0; i<n; i++) > > { > > for(j=0; j<n; j++){ > > find min, max > > } > > if(min<prev_min && max > prev_max){ > > no_min_max=i; > > break; > > } > > else if(min < prev_min){ > > min_row=i; > > } > > else if(max>prev_max){ > > max_row=i; > > } > > } > > if(no_min_max!=-1){ > > i=0; > > while(i!=min_row && i!=max_row) > > i++; > > no_min_max=i; > > } > > > print no_min_max row; > > > *Algo 2:* > > > 1. Copy elements into a linear array > > > 2. Find min and max. O(n) > > > 3. for(i=0; i<rows; i++){ > > > serach for min, max in the ith row; O(n) > > if (both not found) > > break; > > } > > > print the ith row; > > > Which 1 is better??? > > > -- > > 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.
