23ms java code with using binary search of sub MxM matrix


  • 0
    S
    public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        return searchMatrix(matrix, target, 0, 0);
    }
    
    private boolean searchMatrix(int[][] matrix, int target, int startRowIdx, int startColIdx) {
        if((startRowIdx >= matrix.length) || (startColIdx >= matrix[0].length)) { 
            return false; 
        }
        
        // binarySearch for square 
        int size = Math.min(matrix.length - startRowIdx, matrix[0].length - startColIdx); 
        
        int matrixEndRow = startRowIdx + size -1; 
        int matrixEndCol = startColIdx + size -1;
        
        boolean isFound = false; 
        if(target == matrix[matrixEndRow][matrixEndCol]) {
            isFound = true;  
        } else if(target < matrix[matrixEndRow][matrixEndCol]) { 
            isFound = binarySearchMatrix(matrix, target, startRowIdx, startColIdx, size);    
        }
        
        // MxM sub matrix for remain 
        if(!isFound){
            isFound = (searchMatrix(matrix, target, matrixEndRow + 1, startColIdx) 
                        || searchMatrix(matrix, target, startRowIdx, matrixEndCol +1));
        }
        return isFound; 
    }
    
    private boolean binarySearchMatrix(int[][] matrix, int target, int startRow, int startCol, int size) {
        if (size == 0) return false; 
        if (size == 1) {
            return (matrix[startRow][startCol] == target)? true : false; 
        }
        
        int minHalf = size/2;
        int maxHalf = size - minHalf; 
        int mid = matrix[startRow + minHalf][startCol + minHalf]; 
        
        boolean isFound = false;
        if(mid == target) { // if mid has a target value
            return true; 
        } else if(target < mid) { // if target is smaller than mid, then binary search for the top,left quarter
            isFound = binarySearchMatrix(matrix, target, startRow, startCol, minHalf);
        } else { //if target is larger than mid, then binary search for the bottom, left quarter
            isFound = binarySearchMatrix(matrix, target, startRow + maxHalf, startCol + maxHalf, minHalf);
        }
        
        // binary search top,right & bottom,left as smaller or larger values can be found 
        if(!isFound) {
            boolean topRight = binarySearchMatrix(matrix, target, startRow, startCol + minHalf, maxHalf); 
            boolean bottomLeft = binarySearchMatrix(matrix, target, startRow + minHalf, startCol, maxHalf);
            isFound = (topRight || bottomLeft);
        }
        return isFound; 
    }   
    

    }


Log in to reply
 

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