Is this solution's time complexity O(log(m*n))? I'm confused


  • 0
    O
    public static boolean searchMatrix(int[][] matrix, int target) {
            int row = matrix.length - 1;
            int col = matrix[0].length - 1;
            return helper(matrix,target,0,row,0,col);
        }
        
        public static boolean helper(int[][] matrix, int target, int row_start, int row_end, int column_start, int column_end){
            if(row_start > row_end || column_start > column_end){
                return false;
            }
    
            if(row_start == row_end && column_start == column_end){
                if(matrix[row_start][column_start] == target)
                    return true;
                return false;
            }
            int rmid = (row_start + row_end) / 2;
            int cmid = (column_start + column_end) / 2;
            if(matrix[rmid][cmid] == target){
                return true;
            }
            else if(matrix[rmid][cmid] > target){
                return helper(matrix,target,row_start,row_end,column_start,cmid-1) || helper(matrix,target,row_start,rmid-1,cmid,column_end);
            }
            else{
                return helper(matrix,target,row_start,row_end,cmid+1,column_end) || helper(matrix,target,rmid+1,row_end,column_start,cmid);
            }
        }
    

Log in to reply
 

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