AC Java solution with divide and conquer(Follow the hide tags)


  • 0
    _

    BST is a nice method, I was write another method following the hide tags.


    public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
    	int n = matrix[0].length;
    	if(target < matrix[0][0]) return false;
    	if(target > matrix[m - 1][n - 1]) return false;
    	return searchMatrixHelper(matrix, target, 0, 0);
    }
    
    private static boolean searchMatrixHelper(int[][] matrix, int target, int i,
    		int j) {
    	int m = matrix.length;
    	if(i >= m) return false;
    	int n = matrix[0].length;
    	
    	while(matrix[i][n - 1] < target) i++;
    	return searchMatrixHelper(matrix, target, i + 1, j)||searchInRow(matrix, target, i, j);
    }
    
    private static boolean searchInRow(int[][] matrix, int target, int i, int j) {
    	int n = matrix[0].length;
    	int start = j;
    	int end = n - 1;
    
    	while(start <= end){
    		int mid = (start + end)/2;
    		if(target == matrix[i][mid]) return true;
    		if(target > matrix[i][mid]) start = mid + 1;
    		else end = mid - 1;
    	}
    	return false;
    }
    

    }


  • 0

    Nice solution. I think the time complexity here is O(mlogn).
    It is very similar to follow up of lc162 find peak element that to find peak element in a 2D matrix.


Log in to reply
 

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