My O(m log n) C++ solution


  • 0
    V

    The basic idea is converging the max column boundary using binary search while traversing from first to last row

    class Solution {
    public:
       bool searchMatrix(vector<vector<int>>& matrix, int target) 
       {
       int colMax = matrix[0].size() - 1;
            for( int i = 0; i < matrix.size(); ++i )
            {
            int colMin = 0;
                while( colMin < colMax )
                {
                int colMid = ( colMin + colMax + 1) / 2; 
                    if( matrix[i][colMid] <= target )
                    {
                    colMin = colMid;
                    }
                    else
                    {
                    colMax = colMid - 1;
                    }
                }
                if( matrix[i][colMin] == target )
                {
                return true;
                }
            }
        return false;
        }
    };

Log in to reply
 

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