O(log m+log n ) time complexity using java


  • -2
    C
    public class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            if(matrix==null||matrix.length==0||matrix[0].length==0) return false;
            return helper(matrix,target,0,matrix.length-1,0,matrix[0].length-1);
        }
        public boolean helper(int[][] matrix, int target,int rowS,int rowE,int colS,int colE){
            if((rowS>rowE) ||(colS >colE)){
                return false;
            }
            else if(Math.abs(rowE-rowS)<2 &&Math.abs(colE-colS)<2){
                for(int i=rowS; i<=rowE; i++){
                    for(int j=colS;j<=colE;j++){
                        if(matrix[i][j]==target) return true;
                    }
                }
                return false;
            }
            else if((rowS <= rowE) && (colS <= colE)){
                int rmid=(rowS+rowE)/2; int cmid=(colS+colE)/2;
                if(matrix[rmid][cmid]==target) return true;
                else if(matrix[rmid][cmid]>target){
                    if(helper(matrix,target,rowS,rmid,colS,cmid)) return true;
                    else if(helper(matrix,target,rmid+1,rowE,colS,cmid-1)) return true;
                    else if(helper(matrix,target,rowS,rmid-1,cmid+1,colE)) return true;
                    return false;
                }
                else{
                    if(helper(matrix,target,rmid,rowE,cmid,colE)) return true;
                    else if(helper(matrix,target,rmid+1,rowE,colS,cmid-1)) return true;
                    else if(helper(matrix,target,rowS,rmid-1,cmid+1,colE)) return true;
                    return false;
                }
            }
            else{
                return false;
            }
        }
    }

Log in to reply
 

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