c++ - Return the count of negative numbers in the optimal way -

a variation of "searching in matrix sorted rowwise , columnwise"

given 2d matrix sorted rowwise , columnwise. have return count of negative numbers in optimal way.

i think of solution

1. initialise rowindex=0

2. if rowindex>0 rowindex++
   else apply binary search

and implemented in code 5x5 matrix

#include<iostream> #include<cstdio> using namespace std; int arr[5][5];  int func(int row) {     int hi=4;     int lo=0;     int mid=(lo+hi)/2;     while(hi>=lo)     {         mid=(lo+hi)/2;         .         if(mid==4)         {             return 5;         }         if(arr[row][mid]<0 && arr[row][mid+1]<0)         {             lo=mid+1;         }         else if(arr[row][mid]>0 && arr[row][mid+1]>0)         {             hi=mid-1;         }         else if(arr[row][mid]<0 && arr[row][mid+1]>0)         {             return mid+1;         }     } }  int main() {     int ri,ci,sum;     ri=0;   //rowindex     ci=0;   //columnindex     sum=0;     for(int i=0; i<5; i++)     {         for(int j=0; j<5; j++)         {             cin>>arr[i][j];         }     }     while(ri<5)     {         if(arr[ri][ci]>=0)         {             ri++;         }         else if(arr[ri][ci]<0)         {             int p=func(ri);             sum+=p;             ri++;         }     }     printf("%d\n",sum); } 

i ran code here http://ideone.com/pilnd2 runtime o(xlogy) matrix of x rows , y columns

correct me if wrong in time complexity or implementation of code

does have better idea improve run-time complexity?

o(m+n) algorithm, m , n dimensions of array, working sliding down top of negative portion, finding last negative number in each row. prashant talking in comments:

int negativecount(int m, int n, int **array) {     // array pointer m pointers n ints each.     int count = 0;     int j = n-1;     (int = 0, < m; i++) {         // find last negative number in row i, starting index of         // last negative number in row i-1 (or n-1 when i==0).         while (j >= 0 && array[i][j] >= 0) {             j--;         }         if (j < 0) {             return count;         }         count += j+1;     }     return count; } 

we can't better worst-case o(m+n), if you're expecting far fewer m+n negative numbers, may able better usual-case time.

suppose have n n array, array[i][j] < 0 iff i < n-j. in case, way algorithm can tell array[i][n-1-i] < 0 looking @ cell. thus, algorithm has @ at least n cells.