Question

link

Write an efficient algorithm that searches for a value in an n x m table (two-dimensional array). This table is sorted along the rows and columns — that is,

Table[i][j] ≤ Table[i][j + 1],
Table[i][j] ≤ Table[i + 1][j]

Related questions

Search a 2D Matrix.

Searching a 2D Sorted Matrix.

Count negative in a 2D Sorted Matrix.

Analysis

This is a very similar question as prevous one. The solution is O(n) with a linear walk from top-right to bottom-left.

Code

int countNegatives(int array[][], int size) {
    int col = size - 1, row = 0;
    int count = 0;

    while(row < size && col >= 0) {
        if(array[row][col] < 0 ) {
            count = count + (col + 1);
            row = row + 1;
        }
        else {
            col = col - 1;
        }
    }
    return count;
}