Short 11 lines recursive Java, O(log(m*n)) by Binary Search, 1ms


  • 1

    The idea is to consider the matrix as a 1D array and then do Binary Search.

    public class Solution {
    public boolean helper(int[][] matrix, int target, int l, int r) {
        int m = (l+r)/2;
        int a = matrix[m/matrix[0].length][m%matrix[0].length];
        if (target==a) return true;
        if (l==r) return false;
        if (target<a) return helper(matrix,target,l,m);
        else return helper(matrix,target,m+1,r);
    }
    public boolean searchMatrix(int[][] matrix, int target) {
        return helper(matrix, target, 0, matrix.length*matrix[0].length-1);
    }
    

    }


  • 1
    A

    It should be O(log(mn)) or O(log(m)+log(n)),not O(log(m+n))


  • 0

    Thanks, my mistake.


Log in to reply
 

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