assuimg the array is sorted like....each number below is less than the one above and more than the one right to it....
start from the bottom right ..start moving right until u reach anumber less than zero....calcuate the num of negative elements in that row(n-current columng pos)..and then move upwards until u find one higher than zero..while moving keep on counting the numbr of negative elemts in that row..(n-current columng pos)...and then again move right from there...go on in this format until u reach some end.... On Sun, Jun 6, 2010 at 8:57 AM, Minotauraus <anike...@gmail.com> wrote: > 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<algogeeks%2bunsubscr...@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 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.
