Share my O(n + m) solution


  • 6
    O
      Solution {  public:
        bool searchMatrix(vector<vector<int> > &matrix, int target) {
            int n = (int)matrix.size();
            int m = (int)matrix[0].size();
            --n; --m;
            while(n > 0 && matrix[n - 1][m] >= target) --n;
            while(m > 0 && matrix[n][m - 1] >= target) --m;
            return (matrix[n][m] == target);
        }
    };
    

    I just used that fact, that number in the matrix increases


  • 0
    D

    Good job, bro!


  • 7
    D

    I think your solution is not optimal!
    The solution below has O(lonN + logM) time complexity.
    idea is very similar to your but I used bin_search.

    class Solution {
    public:
        bool searchMatrix(vector<vector<int> > &matrix, int target) {
            int n = matrix.size() - 1, m = matrix[0].size() - 1;
            int l = 1, r = n;
            // Let's find a row where may be our target
            while (l <= r){
                int mid = l + (r - l) / 2;
                if (matrix[mid - 1][m] == target) return true;
                if (matrix[mid - 1][m] > target) r = mid - 1; else l = mid + 1;
            }
            int row = r;            
            l = 0, r = m;
            while (l <= r){
                int mid = l + (r - l) / 2;
                if (matrix[row][mid] == target) return true;
                if (matrix[row][mid] > target) r = mid - 1; else l = mid + 1;
            }
            return false;
        }
    };

  • 0
    M

    why you start at the second row( int l = 1, r = n;) when find the row may contain the target?
    I can not figure out why my solution get RE, just a little different from yours. In my solution, I assign the low = 0.


  • 0
    D

    It allows me not to go out from array. You should notice that I consider matrix[mid - 1][m].


  • 0
    A

    Although not optimal solution ,still is a very well though one


Log in to reply
 

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