Question: Given an n X n array with rows sorted and cols sorted, find the number of negative elements in most efficient way

Solution: Assuming indexes in the range 1...N,start at (1,N) ,i.e. right hand top and check if the element is negative.If yes,obviously all the elements on its left including itself would be -ve.So set the count_of_negatives to N and increment the row_index.If a(1,N) is >=0,decrement the col_index.

So at any general grid point , if a(row,col)< 0, increment row by 1 and count_of_negatives by col,because all the elements to the left of a(row,col) including itself in the same row would be < 0. On the other hand if a(row,col) >=0, just decrement col. Execute the above in a loop till you transcend the boundaries of the matrix.

Time Complexity is 2n which is O(n),where n is number of rows(cols) in the square matrix

The pseudocode is

numNegatives(a[1..N][1...N]){

if a(1,1) >= 0 return 0;

if a(N,N) < 0 return N*N;

row = 1
col = N
count = 0; //count is the number of negatives in the matrix
while( row <=N && col >= 1 ){
if(a(row,col) < 0){
count += col; //everything on the left of a(row,col)including itself are -ve
row++;
}else{
col--;
}
}

return count;
}