My C++ solution 9ms and beats 100%, using binary search and treating matrix as sorted vector


  • -1
    C
    class Solution {
    public:
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            const int col = matrix.size();
            if(!col) return false;
            const int raw = matrix[0].size();
            if(!raw) return false;
            
            const int size = col * raw;
            int lo = 0, hi = size;
            while(lo < hi)
            {
                int mi = (lo + hi) >> 1;
                int loCol = lo / raw, loRaw = lo % raw, miCol = mi / raw, miRaw = mi % raw, hiCol = hi / raw, hiRaw = hi % raw;
                if(matrix[miCol][miRaw] < target) lo = mi + 1;
                else if(matrix[miCol][miRaw] == target) return true;
                else hi = mi;
            }
            return false;
        }
    };
    

Log in to reply
 

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