[YAAQ] Monotonically increasing 2-d array.

Question

Give an algorithm to find a given element x (give the co-ordinates), in an n by n matrix where the rows and columns are monotonically increasing.

My thoughts: Reduce problem set size.

In the 1st column, find the largest element <= x. We know x must be in this row or after (lower). In the last column of the matrix, find the smallest element >= x. We know x must be in this row or before. Do the same thing with the first and last rows of the matrix. We have now defined a sub-matrix such that if x is in the matrix at all, it is in this sub-matrix. Now repeat the algo on this sub-matrix... Something along these lines.

[YAAQ: Yet another arrays question.]

Answer 1

If "the rows and columns are monotonically increasing" means that the values in each (row,col) increase such that for any row, (rowM,col1) < (rowM,col2) < ... < (rowM,colN) < (rowM+1,col1) ...

Then you can just treat it as a 1 dimensional array that is sorted from smallest to largest, and do a standard binary search, by sampling the item that is 1/2(rows * cols) fron the start, then sampling the element that is 1/4(rows * cols) behind (if the first element sampled is > x) or ahead (if the first element sampled is < x), and so forth.

Answer 2

Pick a corner element, one that is greatest in its row and smallest in its column (or the other way). Compare with x. Depending on the result of the comparison, you can exclude the row or the column from further search.

The new matrix has sum of dimensions decreased by 1, compared to the original one. Apply the above iteratively. After 2*n steps you end up with a 1x1 matrix.

Answer 3

I think you cannot hope for more than O(N), which is attainable. (N is the width of the matrix).

Why you cannot hope for more

Imagine a matrix like this:

0 0 0 0 0 0 ... 0 0 x
0 0 0 0 0 0 ... 0 x 2
0 0 0 0 0 0 ... x 2 2
.....................
0 0 0 0 0 x ... 2 2 2
0 0 0 0 x 2 ... 2 2 2
0 0 0 x 2 2 ... 2 2 2
0 0 x 2 2 2 ... 2 2 2
0 x 2 2 2 2 ... 2 2 2
x 2 2 2 2 2 ... 2 2 2

where x is an unknown number (not the same number, ie. it might be a different one in every column). To satisfy the monotonicity of the matrix, you can place any of 0, 1, or 2 in all of the x places. So, to find if there is 1 in the matrix, you have to check all the x places, and there are N of them.

How to make it O(n)

Imagine you have to find first column indicies with number > q (a given number) for all rows. You start in the upper right corner of the matrix; if the number you see is greater, you go left; else go down. End when you are in the last row. The points where you went down are the places you search for. If any of them have the number you search for, you've found it.

This algorithm is O(n), because in each step, you either go left or down. Totally, it cannot go more than N times left and N times down. Therefore it's O(n).