Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix, return the occurrence of it.

This matrix has the following properties:

• Integers in each row are sorted from left to right.
• Integers in each column are sorted from up to bottom.
• No duplicate integers in each row or column.

Example:

Consider following example:

[

  [1, 3, 5, 7],

  [2, 4, 7, 8],

  [3, 5, 9, 10]

]

Given target = 3, return 2.

Challenge:

O(m+n) time and O(1) extra space

Solution:

We should start from right top or left bottom. Assume we start with right top, if target is less than current, we could move current to left by 1. If target is greater than current, we could move to bottom by 1. If target is equal to current, we increase the counter and move to left bottom by 1 on each direction. Note: this is not a strict binary search.

Code:

public int searchMatrix(int [][] matrix, int target) {
    if (matrix == null || matrix.length == 0) {
        return 0;
    }
    int m = matrix.length;
    int n = matrix[0].length;
    int i = 0;
    int j = n - 1;
    int count = 0;
    while (i < m && j >= 0) {
        if (matrix[i][j] > target) {
          j--;
        } else if (matrix[i][j] < target) {
            i++;
        } else {
            count++;
            i++;
            j--;
        }
    }
    return count;
}