74. Search a 2D Matrix

From software engineering exercise from leetcode, we have today a search one. https://leetcode.com/problems/search-a-2d-matrix/

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

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -104 <= matrix[i][j], target <= 104

Result:

Success
Details
Runtime: 2 ms, faster than 7.42% of Java online submissions for Search a 2D Matrix.
Memory Usage: 38.4 MB, less than 58.14% of Java online submissions for Search a 2D Matrix.

Solution:

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        //validate input
        if(matrix == null || matrix.length == 0){
            return false;
        }
        //binary search vertical to find row
            // find the max row that is smaller than target
        int yAxis=binarySearchVertical(matrix,target);
        //find the column of target
            //binary search horizontally
        int xAxis=binarySearchHorizontally(matrix,yAxis,target);
        int value=matrix[yAxis][xAxis];
        System.out.println(value);
return value==target;
    }
    
    public int binarySearchHorizontally(int[][] matrix, int yAxis, int target){
        int l=0,
            r=matrix[yAxis].length-1;
        int maxColumn=0;
        while(l<=r){
            int m = l+(r-l)/2;
            if(matrix[yAxis][m] <= target){
                //my number could be in this column, 
                maxColumn=Math.max(maxColumn,m);
                //but probably also higher
                l=m+1;
            }else{
                //crrrent is higher, search lower
                r=m-1;
            }
        }
        return maxColumn;
    }
    
    
    public int binarySearchVertical(int[][] matrix, int target){
        int l=0,
            r=matrix.length-1;
        int maxRow=0;
        while(l<=r){
            int m = l+(r-l)/2;
            if(matrix[m][0] <= target){
                //my number could be in this row, 
                maxRow=Math.max(maxRow,m);
                //but probably also higher
                l=m+1;
            }else{
                //crrrent is higher, search lower
                r=m-1;
            }
        }
        return maxRow;
    }
}

Update

After overthinking a better solution could have been implemented thinking of the matrix as a nxm list.

Result:

Success
Runtime: 0 ms, faster than 100.00% of Java online submissions for Search a 2D Matrix.
Memory Usage: 38.2 MB, less than 92.51% of Java online submissions for Search a 2D Matrix.

Solution:

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        //validate input
        if(matrix == null || matrix.length == 0){
            return false;
        }
    int m = matrix.length;
    int n = matrix[0].length;
        
    int left = 0;
    int right = m * n - 1;
    while (right - left >= 0) {
        int middle = left + (right - left) / 2;
        int middleEl = matrix[middle / n][middle % n];
        if (middleEl == target)
            return true;
        if (middleEl > target)
            right = middle - 1;
        else
            left = middle + 1;
    }
    return false;
    }
    
}