240. Search a 2D Matrix II

Write an efficient algorithm that searches for a target value in an m x n integer matrix. The matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

Example 1:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true

Example 2:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
Output: false

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= n, m <= 300
• -109 <= matix[i][j] <= 109
• All the integers in each row are sorted in ascending order.
• All the integers in each column are sorted in ascending order.
• -109 <= target <= 109

Result:

Success
Details
Runtime: 10 ms, faster than 17.72% of Java online submissions for Search a 2D Matrix II.
Memory Usage: 51.8 MB, less than 5.22% of Java online submissions for Search a 2D Matrix II.

Solution:

Runtime Complexity: O(nlogn)
Space complexity: O(1)

class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
        
        //binary search horizontally
            //check if range is good
            //binary search vertically
                //if found -> wuju
                //else -> move 
        for(int i =matrix.length-1; i >=0 ;i--){
            if( isInRange(matrix[i],target) ){
                //binary vertically
                int pos = binaryVertical(matrix[i],target);
                if(pos != -1){
                    return true;
                }
            }
        }
        return false;
    }
    
    boolean isInRange(int[] matrix, int target){
        return ( (matrix[0] <= target) && (matrix[matrix.length-1] >= target) );
    }
    
    int binaryVertical(int[] matrix, int target){
        int l=0, 
            r=matrix.length-1;
        while(l <= r ){
            int m = l+(r-l)/2;
            if(matrix[m] == target ){
                return m;
            }
            if(matrix[m] < target){  // my target is larger,  move left pointer to right
                l = m + 1;
            }else{                   // my target is smaller, move right pointer to left
                r = m - 1;
            }
        }
        return -1;
    }
    
    
    
}

A more appropriate solution could be:

Result:

Success
Details
Runtime: 10 ms, faster than 17.72% of Java online submissions for Search a 2D Matrix II.
Memory Usage: 51.2 MB, less than 11.01% of Java online submissions for Search a 2D Matrix II.

Solution:

Runtime Complexity: O(n+m)
Space complexity: O(1)

class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
        int i =0, 
            j = matrix[0].length-1;
        while( i < matrix.length && j >=0 ){
            if(target == matrix[i][j]){
                return true;
            }
            if(target < matrix[i][j]){
                j--;
            }else{
                i++;
            }
        }
        return false;
    }  
}