240. Search a 2D Matrix II

https://leetcode.com/problems/search-a-2d-matrix-ii/

Solution:

An interesting question. Let look at element Matrix[x][y]. All the elements in the up-left region are smaller; and all the elements in the down-right region are larger. And the rest two parts (up-right and down-left) are unknown. However, if we start from the most down-left corner, or the most up-right corner, only one unknown region will left initially. Let's choose the most up-right corner as the starting point. If Matrix[x][y] is larger than target, --y; else if Maxtrix[x][y] is smaller than target, ++ x; else if Matrix[x][y] equals to target, return true. If no element can be found after scanning, return false.

Code:

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.empty() || matrix.front().empty()) return false;
        int m = matrix.size(), n = matrix.front().size(), x = 0, y = n-1;
        while(x<m && y>=0){
            if(matrix[x][y] == target) return true;
            else if(matrix[x][y] < target) ++x;
            else --y;
        }
        return false;
    }
};