Searching a 2D Array at sublinear time

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:

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

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.

I guess you could do binary search on each row. That would be O(m * log(n)). — marstran, Apr 23 '16 at 20:12
Each row is redundant. Note that in each submatrix, bottom right element is the maximum. Thus you can, for example, traverse the main diagonal to find the first value V that is higher than the search pattern. The search pattern should reside somewhere in the complement to the square submatrix from top left corner to V. — bipll, Apr 23 '16 at 21:05
@bipll: the question asks for an m x n matrix, so there may not be a diagonal (which is appropriate for a square matrix). — stackoverflowuser2010, Apr 23 '16 at 21:17
@stackoverflowuser2010 Nevertheless this holds true for any set of dimensions, and m[k][k] is the largest of all m[i][j], 0 ≤ i, j ≤ k. — bipll, Apr 24 '16 at 05:36

Maljam · Answer 1 · 2016-04-23T21:29:37.920

2

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.

edited Apr 23 '16 at 21:29

answered Apr 23 '16 at 20:13

Maljam

6,244
3
17
30

2

Nice idea, but isn't this still O(n)? If you happen to look for the largest value, you would still need to look through all the values, wouldn't you? – marstran Apr 23 '16 at 20:16
@marstran good point, I guess I could still improve it by somehow merging it with the "symmetrical algotritm" where you would start in the opposite corner.. I'll think about it.. – Maljam Apr 23 '16 at 20:19
@marstran I changed the algorithm a little, now it should be sub-linear. Do you agree? – Maljam Apr 23 '16 at 20:58
Hmm, what would happen if you would search for 25 in this matrix? `[[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15], [16, 17, 18, 19, 20], [21, 22, 23, 24, 25]]`. Would the algorithm still search through all values in this case? – marstran Apr 23 '16 at 21:25
@marstran it will search through the whole first row, and then check for the value below 5 (10), if it's smaller than 25, it'll skip that row, and then check for the value below 10 (15), and skip again until it reaches 25 – Maljam Apr 23 '16 at 21:28
I think this can search an entire top-left triangle of a matrix, which has area O(mn) or O(n^2) or some such. – mjwach Apr 23 '16 at 21:31

mjwach · Answer 2 · 2016-04-23T21:24:56.227

For a given value x, there is a boundary wandering through the matrix, more or less from lower-left to upper-right, always proceeding right or up, and separating values greater than x from values less than or equal to x.

Start from upper left and search down and right in a straight diagonal line until this jagged boundary is found. (If a border of the matrix is reached first, simply follow that border right or down, continuing the search.) Then step along the boundary in both directions until x is found or there are no more matrix cells to search.

This search can traverse three path sections, each of which only goes right-and-down, right-and-up, or left-and-down. Such paths' lengths are O(m+n). Thus the whole search is O(m+n).

Searching a 2D Array at sublinear time

2 Answers2