240. Search a 2D Matrix II

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.

For example,

Consider the following matrix:

[
  [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]
]

Given target = 5, return true.

Given target = 20, return false.

Solution:

The row is in ascending order and the column is also in ascending order.

So we can start from the bottom left.

If the target is smaller than the current point, the matching point can only be in the above area.

We go up.

If the target is target than the current point, the matching point can only be int he right area.

We go right.

The time complexity is O(m + n) and the space complexity is O(1).



Code:

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) {
            return false;
        }
        if (matrix[0] == null || matrix[0].length == 0) {
            return false;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        
        int x = m - 1;
        int y = 0;
        while (x >= 0 && x < m && y >= 0 && y < n) {
            if (matrix[x][y] == target) {
                return true;
            }
            else if (matrix[x][y] < target) {
                y++;
            }
            else {
                x--;
            }
        }
        return false;
    }
}