240. Search a 2D Matrix II

Description

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.

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

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

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

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : O(1)
 */

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

Solution 2

/**
 * Time complexity : O(n+m)
 * Space complexity : O(1)
 */

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

Follow up