Running Time of code??


  • 0
    P

    Time Complexity of following code is better than O(m+n) but still the actual running time is very bad. Why?

    public class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix==null) return false;
        int m = matrix.length;
        if(m==0) return false;
        int n = matrix[0].length;
        if(n==0) return false;
    
        return searchSubMatrix(matrix,0,m,0,n,target);
        }
    
        private boolean searchSubMatrix(int[][] matrix, int row_start, int row_end, int col_start, int col_end, int target) {
        if(row_end==row_start+1)
            return Arrays.binarySearch(matrix[row_start],col_start,col_end,target)>=0;
        if(col_end==col_start+1){
            int[] array = new int[row_end];
            for (int i = row_start; i < row_end; i++) {
                array[i] = matrix[i][col_start];
            }
            return Arrays.binarySearch(array,row_start,row_end,target)>=0;
        }
        int[] array1 = new int[row_end];
        int[] array2 = new int[row_end];
        for (int i = row_start; i < row_end; i++) {
            array1[i] = matrix[i][0];
            array2[i] = matrix[i][col_end-1];
        }
        int row_end_new = Arrays.binarySearch(array1,row_start,row_end,target);
        if(row_end_new>=0) return true;
        row_end_new = -(row_end_new+1);
        if(row_end_new==0) return false;
    
        int row_start_new = Arrays.binarySearch(array2,row_start,row_end,target);
        if(row_start_new>=0) return true;
        row_start_new = -(row_start_new+1);
        if(row_start_new>=row_end) return false;
    
        int col_end_new = Arrays.binarySearch(matrix[row_start],col_start,col_end,target);
        if(col_end_new>=0) return true;
        col_end_new = -(col_end_new+1);
        if(col_end_new==0) return false;
    
        int col_start_new = Arrays.binarySearch(matrix[row_end-1],col_start,col_end,target);
        if(col_start_new>=0) return true;
        col_start_new = -(col_start_new+1);
        if(col_start_new>=col_end) return false;
    
        return searchSubMatrix(matrix,row_start_new,row_end_new,col_start_new,col_end_new,target);
       }
    }

Log in to reply
 

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