Thread: Count number of negative integers

Count number of negative integers in left-to-right and top-to-bottom sorted 2D array (matrix).

Assuming matrix is sorted left-right and top-to-bottom in increasing order.

Code:

int 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;
}