Find number in sorted matrix (Rows n Columns) in O(log n)

Question

Say I have a matrix (MxN) which has its rows and columns sorted.

1. All the elements in each row are arranged in increasing order
2. All the elements in each column are arranged in increasing order
3. All the elements are integers

4. No other assumptions can be made

   Example:

   [1 5 8 20]

   [2 9 19 21]

   [12 15 25 30]

I have to find if a given number is present in the matrix or not (Basic search). I have an algorithm which runs O(n)

int row = 0;
int col = N-1;

while (row < M && col >= 0) {
  if (mat[row][col] == elem) { 
    return true;
  } else if (mat[row][col] > elem) { 
    col--;
  } else { 
    row++;
  } 
}

But I was asked an O(log (MxN)) == O(Log(n)) solution. Any ideas??

Answer 1

O(log (M * N)) solution is not possible for this task.

Let's look at a simplified task: in "sorted" square matrix assume all elements above secondary diagonal (green) less than given number, all elements below secondary diagonal (red) greater than given number, and no additional assumptions for elements on secondary diagonal (yellow).

Neither original assumptions of this task, nor these additional assumptions tell us how elements on secondary diagonal are related to each other. Which means we just have an unsorted array of N integers. We cannot find given number in the unsorted array faster than O(N). So for original (more complicated) problem with square matrix we cannot get a solution better than O(N).

For a rectangular matrix, stretch the square picture and set the additional assumptions accordingly. Here we have min(N,M) sorted sub-arrays of size max(N,M)/min(N,M) each. The best way to search here is to use linear search to find one or several sub-arrays that may contain given value, then to use binary search inside these sub-arrays. In the worst case it is necessary to binary-search in each sub-array. Complexity is O(min(N,M) * (1 + log(max(N,M) / min(N,M)))). So for original (more complicated) problem with rectangular matrix we cannot get a solution better than O(min(N,M) * ( 1 + log(max(N,M)) - log(min(N,M)))).

Answer 2

It is not possible to do better than O(n). Some guys (there are at least three of them on this page) think they can do better but that's because their algorithms are wrong or because they don't know how to compute the complexity of their algorithm so they try to guess it. This blog post is very good and will explain you the errors of these guys.

Draft of a proof that O(n) is optimal: consider the following matrix:

1     2     3     4     5     6 … (n-2)  (n-1) (n+1)
2     3     4     5     6     7 … (n-1)  (n+1) (n+2)
3     4     5     6     7     8 … (n+1)  (n+2) (n+3)
…     …     …     …     …     … … …      …     …
(n-2) (n-1) …     …     …     … … …      …     (2n-1)
(n-1) (n+1) …     …     …     … … …      …     2n
(n+1) (n+2) …     …     …     … … (2n-1) 2n    (2n+1)

If you are looking for n in this matrix you must check at least once for each row if n is in the row because n could be in any row. (The proof is not complete but here is the idea)

Answer 3

You have to use recursion to solve this problem. Given a matrix X and number y, you can do binary search for y on the middle row of X and divide the matrix into four parts such that:

A|B
---
C|D

all elements in A are less than y, all elements in D are greater than y, and y can be in B and C. Iteratively find y in B and C.

Since height(A)=height(B)\approx= height(C)=height(D), size(X)>= 2*(size(B)+size(C)) . So the resulting complexity if O(logn).

def find(X,y):
    a,b = X.shape
    i = a /2
    j = binsearch(X[i,:], y)
    if X[i,j]==y:
        return True
    else:
        return find( X[ (i+1):a, 0:(j-1)], y ) or find( X[ 0:i, j:b], y )

Answer 4

Since both rows and columns are sorted, if we look at the first element of each row we can find which one contains the number we're looking for. Then, again, we can exploit the fact that the elements in each row are sorted and find that number.
The fastest search algorithm I know is Binary Search, which has a complexity of O(log n), so the total complexity will be O(log m + log n).
Here's an example, suppose we're looking for 28:

 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 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50

• We do a binary search over the elements of the first column (1, 11, 21, 31, 41) and find that the row is the third, because its first element is smaller than our number but the next row's first element is larger. Number of steps: 2 (21, 31, found)
• We do a binary search again over the third row (21, 22, 23, 24, 25, 26, 27, 28, 29, 30) and find our number. Number of steps: 2 - 3 (25, 27 or 28, found)

Answer 5

I think this can be done in O(log(n*n)*log(n)) time, where n is the no. of the rows of a square matrix.

By the properties of Matrix, the principal diagonal of the matrix is a sorted array. So, we can search an element or its lower bound in O(log(n)). Now, using this element as pivot, we have 4 sub-matrix. and we can say that all the elements in sub-matrix(top-left) are smaller, all the elements in sub-matrix (lower-right) are bigger. So, we can remove that from the search space.

Now, recursively search in sub-matrix (top-right) and in sub-matrix(lower-left).

Since, at each step, we perform a log(n) search (along principal diagonal) ad there can be atmost log(n*n) steps (as we reduce the search space by half in each step).

So, Time complexity = O(log(n)log(nn)).

Please correct, if anything is wrong.

Refrences - [Book]Cracking the coding interview (Question 11.6)