A slow but worth thinking solution O(n ^ c) where n is the total number of cells and c < 1


  • 0
    B

    Many people had done this with exactly the same idea, but no one seems to have figured out its time complexity so far.

    public boolean searchMatrix(int[][] matrix, int target) {
      int rows = matrix.length;
      int columns = rows != 0 ? matrix[0].length : 0;
      return searchMatrix(matrix, target, 0, columns, 0, rows);
    }
    
    private static boolean searchMatrix(int[][] matrix, int target, int left, int right, int top, int bottom) {
      if(left == right || top == bottom) return false;
      int x = (left + right) / 2;
      int y = (top + bottom) / 2;
      if(matrix[y][x] == target) return true;
      if(matrix[y][x] < target)
        return searchMatrix(matrix, target, x + 1, right, y + 1, bottom)
                 || searchMatrix(matrix, target, left, right, y + 1, bottom)
                 || searchMatrix(matrix, target, x + 1, right, top, bottom);
      else
        return searchMatrix(matrix, target, left, x, top, y)
                 || searchMatrix(matrix, target, left, right, top, y)
                 || searchMatrix(matrix, target, left, x, top, bottom);
    }
    

    For those of you who are not familiar with this idea, this algorithm divides a big problem into 3 smaller problems whose sizes are in average 1/4 of the original problem.

    Many (including me) thought this was binary search and thought the complexity was something near log(n), but that is not correct. The correct way to analyse its complexity is by master theorem:
    T(n) = 3T(0.25n) + O(1) -> T(n) = O(n^(log(4)/log(3))) ~= O(n^0.79)

    It is slightly better than brute force, hence the judge DOES let it pass the test. Hooray!!


Log in to reply
 

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