Java clear solution


  • 18
    S

    The basic idea is from right corner, if the current number greater than target col - 1 in same row, else if the current number less than target, row + 1 in same column, finally if they are same, we find it, and return return.

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

  • 2
    S

    Test case [] should be checked.Otherwise, matrix[0] will ArrayOutofBound.


  • 4
    S

    This is not fully taking advantage of the sorted feature of the matrix, basically we can cut the sort by half, right?


  • 0
    1
    This post is deleted!

  • 3

    The worst case of the above solution runs in O(M+N) but it can be done in O(logM + logN) by taking the advantage of sorting.


  • 1
    M

    Not a binary search.


  • 1
    A

    This is a 2 pointer method and not binary search. Worst case performance is O(mn) which is basically same as looking at each element one by one.

    We are not taking advantage of the sorting already done.
    Using binary search, we can finish in O(log(mn)).


  • 5
    S

    @abhisheak It's not O(mn), the worst case is O(m + n). You don't need to iterate through each column for each row.


Log in to reply
 

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