Searching a 2D Array at sublinear time [duplicate]

Question

This is a problem from a recent coding interview

Write an efficient algorithm that searches for a value in an m x n matrix.

This matrix has the following properties:

1. Integers in each row are sorted in ascending from left to right.

2. Integers in each column are sorted in ascending from top to bottom.
   .

     [1,   4,  7, 11, 15]
   
     [2,   5,  8, 12, 19]
   
     [3,   6,  9, 16, 22]
   
     [10, 13, 14, 17, 24]
   
     [18, 21, 23, 26, 30]
   

Is there a way to do this below O(mn). I can't see how one can do a binary search on this array, since there's no way to eliminate anything.

Answer 1

You can use this simple algorithm that exploits the fact that in a matrix with these properties, a value mtx[i][j] is always smaller than any value mtx[x][y], where x > i or y > j, in other words, any value to the right and down:

public static boolean find(int[][] mtx, int val) {
    int maxCol = mtx[0].length, minCol = 0;

    for(int i = 0 ; i < mtx.length ; i++) {
        for(int j = minCol ; j < maxCol ; j++) {
            if(val == mtx[i][j]) return true;

            if(val < mtx[i][j]) {
                maxCol = j;
                break;
            }
        }

        if(maxCol == 0) break;

        minCol = 0;
        if(i != mtx.length-1 && val > mtx[i+1][maxCol-1]) minCol = maxCol-1;
    }

    return false;
}

The idea is to search row by row, and if you find a value that is larger, you can stop looking in this row and you know that you don't have to search beyond that column in future rows. And if the first value of a row is bigger than the value, than you can stop searching and return false. Also, at the end of each row search, you check for the cell from the next row at maxCol-1, if the value is larger, then in the next cycle, you can skip every cell preceding.

The worst case scenario is the largest value (or larger), and the complexity is O(m+n), because it would check all the first row, and then skip the next m rows.