74. Search a 2D Matrix

Description

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.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

Examples

Example 1

Input:

matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ]

target = 30

Output: true

Example 2

Input:

matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ]

target = 13

Output: false

Solutions

Solution 1

/**
 * Time complexity : O(log(mn)) since it's a standard binary search.
 * Space complexity : O(1).
 */

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int row = matrix.length;
        if(row == 0) return false;
        int col = matrix[0].length;
        if(col == 0) return false;
        for(int[] arr: matrix) {
            if(target <= arr[col-1]) {
                if(arr[col-1] == target || binarySearch(arr, col, target) != -1) {
                    return true;
                }
                break;
            }
        }
        return false;
    }
    private int binarySearch(int[] arr, int n, int target) {
        int low = 0;
        int high = n-1;
        while(low <= high) {
            int mid = (low+high)/2;
            if(arr[mid] == target) {
                return mid;
            } else if(target > arr[mid]) {
                low = mid+1;
            } else {
                high = mid-1;
            }
        }
        return -1;
    }
}

Solution 2

/**
 * Time complexity : O(log(mn)) since it's a standard binary search.
 * Space complexity : O(1).
 */
 
 class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int row = matrix.length;
        if(row == 0) return false;
        int col = matrix[0].length;
        
        // Binary search
        int low = 0, high = row*col-1;
        int pivotIdx, pivotValue;
        while(low <= high) {
            pivotIdx = (low+high)/2;
            pivotValue = matrix[pivotIdx/col][pivotIdx%col];
            if(target == pivotValue) {
                return true;
            } else if(target < pivotValue) {
                high = pivotIdx-1;
            } else {
                low = pivotIdx+1;
            }
        }
        return false;
    }
}

Follow up