Concise O(m+n) C++ solution beating 98%


  • 3
    C

    The idea is to narrow the range of search, which is similar to what binary search is doing. We can start the search from the top right corner of the matrix.

    If current matrix[x][y] < target, we increment x,
    if current matrix[x][y] > target, we decrement y.
    Otherwise, we find target.

    Here's the proof why this is correct.

    When we have matrix[x][y] < target, it means all elements to the top left of (x, y) do not have our target, we call this region top_left
    When we have matrix[x][y] > target, it means all elements to the bottom right of (x, y) do not have our target., we cal this region bottom_right
    And since we are starting from the top right corner, and the above two regions top_left and bottom_right are essentially connected, thus the top_right corner can also be excluded.

    So in other words, at each time the only region could possible have our target is the bottom_left region.

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

    In fact, if we start with bottom left corner, it can also work. Then this means at each position, the region that could possible have the target is actually top right region.

        //start from bottom left
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            if (matrix.size() == 0 || matrix[0].size() == 0) return false;
            int x = matrix.size() - 1;
            int y = 0;
            while (x >= 0 && y < matrix[0].size()) {
                if (matrix[x][y] == target) return true;
                if (matrix[x][y] > target) {
                    x--;
                } else {
                    y++;
                }
            }
            return false;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.