74. Search a 2D Matrix

Problem

Tags: Array, Binary Search, Matrix

Write an efficient algorithm that searches for a value target in an m x n integer matrix 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
• -10^4 <= matrix[i][j], target <= 10^4

Code

C

// 74. Search a 2D Matrix (4/13/54212)
// Runtime: 0 ms (92.69%) Memory: 6.34 MB (17.31%) 

bool searchMatrix (int** matrix, int matrix_size, int* matrix_col_size, int target) {
    int row = 0;
    for (int i = 0; i < matrix_size; i++) {
        if (matrix[i][0] <= target) {
            row = i;
        }
    }
    
    for (int i = 0; i < *matrix_col_size; i++) {
        if (matrix[row][i] == target) {
            return true;
        }
    }
    
    return false;
}

JS

// 74. Search a 2D Matrix (7/1/53723)
// Runtime: 95 ms (21.10%) Memory: 39.58 MB (94.37%) 

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
function searchMatrix(matrix, target) {
    for(let i = 0; i < matrix.length; i++) {
        for(let j = 0; j < matrix[i].length; j++) {
            if(matrix[i][j] === target) return true;
            if(matrix[i][j] > target) return false;
        }
    }
    return false;
};