Java solution in log4/3(N*M);


  • -1
    A
    public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        return searchRec(matrix, target, 0, 0, matrix.length-1, matrix[0].length-1);
    }
    
    private boolean searchRec(int[][] matrix, int target, int loX, int loY, int hiX, int hiY) {
        if (loX < 0 || loY < 0 || hiX >= matrix.length || hiY >= matrix[0].length || loX > hiX || loY > hiY) {
            return false;
        }
        if (loX == hiX && loY == hiY) {
            return target == matrix[loX][loY];
        }
        
        int x = (loX + hiX) / 2;
        int y = (loY + hiY) / 2;
        
        boolean result = false;
        if (matrix[x][y] >= target) {
            result |= searchRec(matrix, target, loX, loY, x, y);
        } else {
            result |= searchRec(matrix, target, x+1, y+1, hiX, hiY);
        }
        result |= searchRec(matrix, target, x+1, loY, hiX, y);
        result |= searchRec(matrix, target, loX, y+1, x, hiY);
        
        return result;
    }
    

    }


  • 0
    Z

    Hi Amisarca,

    Thank you for sharing your solution!

    I had the same idea as yours at the beginning, but in my understanding, the time complexity is (by master theorem):

    T(n) = 3 * T(0/75 * n) + O(1)  ==> O(n ^ log(3, 1.33)) = O (n ^ 3.82)    
    

    where 0.75 is a rough guess but I think is a good estimation (actually 0.75 is the best case).

    So this is not binary search (a = 3 not 1) and it indeed has an unideal time complexity; the top-right to bottom-left search solution is much better.

    Zijiao


  • 0
    P

    Your analysis suggests this algorithm is even worse than the brute force one?


Log in to reply
 

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