74. Search a 2D Matrix

Search a 2D Matrix

Problem Description

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
• -104 <= matrix[i][j], target <= 104

Idea: Binary Search Approach

Let`s Code It!

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matrix, target) {
    let start = 0;
    let m = matrix[0].length; // col
    let n = matrix.length; // row
    let end = m*n-1;
    let mid = start + parseInt((end - start)/2);
    while(start <= end){
        let col = mid % m;
        let row = parseInt(mid / m);
        if(matrix[row][col] == target){
            return true;
        }
        if(matrix[row][col] > target){
            end = mid-1;
        }else{
            start = mid+1;
        }
        mid = start + parseInt((end - start)/2);
    }
    return false;
};

Runtime: 108 ms, faster than 21.13% of JavaScript online submissions for Search a 2D Matrix.
Memory Usage: 42.7 MB, less than 14.57% of JavaScript online submissions for Search a 2D Matrix.

Complexity 

Time Complexity
We are using a binary search approach hence, its complexity is O(log n)


Space Complexity
We are using constant space to store mid, start, and end so O(1)

 B) UP - DOWN Approach

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matrix, target) {
    let m = matrix[0].length; // column length
    let n = matrix.length; // row length
    
    let i = 0; // first row
    let j = m-1; // last column
    
    // till i < n (row o to n) AND j >= 0 (col m to 0)
    while(i<n && j>=0){ 
        if(matrix[i][j] == target){
            return true;
        }
        if(matrix[i][j] > target){
            // we'll be moving towards left if the value of target is smaller 
            j--;
        }else{
            // otherwise we'll be moving downwards if the target is greater than
            i++;
        }
    }
    return false;
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem #74. Search a 2D Matrix 

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to solve leetcode questions & present the most important points to consider when improving Data structure and logic,  feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!