1. check arr[0][0]. If this is non negative, there are 0 negative numbers. (assuming sorting is ascending) 2. for arr[i][j], increment j until you hit a non-negative number. this index will be limitRow 3. increment i, until you hit a non-negative number, this index will be limitColumn, for i<limitRow for j<limitColumn if(arr[i][j] <0) negativeCount++; limitColumn=j; if(limitColumn == 1) break;
This is <O(n) since every element will be checked a max. of 1 time On Jun 5, 12:08 pm, divya <sweetdivya....@gmail.com> wrote: > Given an n X n array with rows sorted and cols sorted, find the number > of negative elements in most efficient way -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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.