28

I have a x by y matrix, where each row and each column are in ascending order as given below.

1   5   7    9
4   6   10   15
8   11  12   19
14  16  18   21

How to search this matrix for a number in O(x+y)?

I was asked this question for an interview, but could not figure out the way. Curious to know if it could be done.

eeerahul
  • 1,629
  • 4
  • 27
  • 38
Ashley
  • 283
  • 3
  • 5
  • sounds similar to this http://geeksforgeeks.org/forum/topic/amazon-interview-question-for-software-engineerdeveloper-about-algorithms-10 – Rohan Monga Sep 16 '10 at 03:17

3 Answers3

42

Start at the last element of the first row(top-right corner).
Compare it with the key. We have 3 cases:

  • If they are equal we are done.

  • If key is greater than that element then it means key cannot be present in that row so move the search to the element below it.

  • If key is less than that element then it means key could be present in that row towards left and cannot be present in the column further down, so move the search to the element left of it.

Keep doing it till you find the element or you cannot further move(key does not exist).

Pseudo code:

Let R be number of rows
Let C be number of columns

Let i = 0
Let j = C-1

found = false
while( i>=0 && i<R) && (j>=0 && j<C) )
   if (matrix[i][j] == key )
      found = true
      break
   else if( matrix[i][j] > key )
       j--
   else if( matrix[i][j] < key )
       i++
end-while
codaddict
  • 445,704
  • 82
  • 492
  • 529
  • I can't see this working. Suppose I am searching for key= 11 in the above array, how does this algo find it? – Ashley Sep 16 '10 at 03:45
  • 2
    @Ashley: We start at `9`. `11` > `9` so move down. `11` < `15` move left. `11` > `10` move down. `11` < `12` move left. `11` == `11` – codaddict Sep 16 '10 at 03:57
  • @codaddict: downvotes never explain any longer :/ This is a classic algorithm for searching in sorted matrices, the basic idea is that you sort the matrix in the direction of one diagonal and iterate along the other. You could therefore start at the lower-left corner too :) – Matthieu M. Sep 16 '10 at 12:19
5

Split the Matrix in 4 submatrices. If bottom right of a sub-matrix is less than key, discard it. If the top left of a sub-matrix is bigger than the key, discard it. Repeat the splitting procedure for the remaining sub-matrices.

[Update] For some pseudo code (and a discussion of complexity) see Jeffrey L Whitledge's answer of this question.

Community
  • 1
  • 1
Landei
  • 54,104
  • 13
  • 100
  • 195
  • That should have even better performance: O(log x + log y) ?! – Andre Holzner Sep 16 '10 at 23:09
  • It might be faster, but needs more memory. – Landei Sep 17 '10 at 06:38
  • How will you split the matrix in 4 submatrices? Till when will you repeat? When will you know that the element is not present? Start writing psuedo code and you will son find that this is not that easy. @Landei - Won't the memory be same as x*y? – Manoj R Sep 20 '10 at 14:00
  • Actually, this will be O(2 ^ log x + 2 ^ log y), as at each step you need to recurse over 2 (or three, but you can improve to avoid that) sub-matrixes. This is O(x + y) – Chris Dodd Oct 13 '10 at 03:24
0
// the matrix is like this, from left to right is ascending, and
// from down to up is ascending, but the second row'start is not always bigger than the first row's end, which is diff from [leetcode]https://oj.leetcode.com/problems/search-a-2d-matrix/
// 1   5   7    9
// 4   6   10   15
// 8   11  12   19
// 14  16  18   21
// time complexity is O(x+y), x is the count of row, and y is the count of column

public boolean searchMatrix2(int[][] matrix, int target) {
    int rowCount = matrix.length;
    if(rowCount == 0) return false;

    int colCount = matrix[0].length;
    if(colCount == 0) return false;

    //first find the target row, needs O(x)
    int targetRow = 0;
    while(targetRow < rowCount-1 && matrix[targetRow+1][0] <= target) {
        targetRow++;
    }
    //than find the target in the target row, needs O(y), so the total is O(x)+O(y)
    boolean result = false;
    for(int i = 0; i < colCount; i ++) {
        if(matrix[targetRow][i] == target) {
            result = true;
            break;
        }
    }
    return result;
}

Actually, we can use binary search twice, find the target row by binary search first, then find the target in the row by binary search, so the time complexity is O(lgx) + O(lgy), is O(lgx + lgy), better the O(x+y).

Converse Chen
  • 9
  • 2