Isn't it the same quiz from CTCI of which solution is O(m+n). C++ code's here.


  • 0
    A

    I think this question's optimal answer is on CTCI. The time complexity is O(N+M).

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

  • 0
    E

    I guess this could be wrong. For example, it cannot return true for searching 5 in matrix in the example.


Log in to reply
 

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