9ms C++ solution without binary reseach, beats 100%


  • 0
    M

    Idea is very straight forward. Actually you can put start point on either top right or bottom left. I chose top right in this case.

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

    I have no idea why it is even faster than binary search, the worst case of my solution is O(sqrt(m^2 + n^2)) which should be mathematically slower than O(log(mn)), may be it's just fast on those test cases :)


    Also came up a binary search solution for 12 ms, hope this helps~

    bool searchMatrix(vector<vector<int>>& matrix, int target) {
            int m = matrix.size(), n = matrix[0].size();
            int left = 0, right = m*n-1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (matrix[mid/n][mid%n] == target) {
                    return true;
                }
                else if (matrix[mid/n][mid%n] < target) {
                    left = mid + 1;
                }
                else {
                    right = mid - 1;
                }
            }
            return false;
        }
    

Log in to reply
 

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