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 <[email protected]> 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 <[email protected]> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[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.
