Clean, Simple and Fast Java Solution 41ms


  • 0
    public class Solution {
        
        private boolean searchMatrixRec(int[][] matrix, int ri, int rj, int ci, int cj, int target) {
            if (ri > rj || ci > cj)
                return false;
            int rmid = ri + (rj-ri) / 2;
            int cmid = ci + (cj-ci) / 2;
            int val = matrix[rmid][cmid];
            if (target > val) 
                return searchMatrixRec(matrix,ri,rj,cmid+1,cj,target) ||
                       searchMatrixRec(matrix,rmid+1,rj,ci,cj,target);
            else if (target < val)
                return searchMatrixRec(matrix,ri,rj,ci,cmid-1,target) ||
                       searchMatrixRec(matrix,ri,rmid-1,ci,cj,target);
            else
                return true;
        }
        
        public boolean searchMatrix(int[][] matrix, int target) {
            return searchMatrixRec(matrix,0,matrix.length-1,0,matrix[0].length-1,target);
        }
    }

  • 0

    Note that divide the matrix into 4-mini matrix and recursive call into 1 of the 4 part is NOT working.... you may miss some value check. Must binary search left-or-right part and top-or-down part simultaneously and OR their outcome.


Log in to reply
 

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