Solving Leetcode 74. Search a 2D 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.
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 Output: true

Basically what its asking is given a 2D matrix of integers, find whether the target is present in the matrix or not. You can solve this problem using either a binary search or a linear search. 1. Binary search: First, find the row where the target is likely to be located using binary search. Then, do a linear search in that row to find the target.

2. Linear search: Simply scan through the matrix until you find the target.

The binary search approach is more optimal, as it has a time complexity of O(log(m) + log(n)), while the linear search approach has a time complexity of O(m * n). This work because the matrix is sorted.

First, we need find the row where the target is likely to be located using binary search. Then, do a linear search in that row to find the target.

We can start by finding the midpoint of the matrix. If the target is less than the element at the midpoint, search the left half of the matrix. If the target is greater than the element at the midpoint, search the right half of the matrix. Repeat this process until you find the row where the target is likely to be located. How do you do the second part? Once you have found the row where the target is likely to be located, you can do a linear search in that row to find the target. Start at the beginning of the row and scan through until you find the target or reach the end of the row.

Code in JavaScript:

var searchMatrix = function(matrix, target) {
          let row = 0;
        let col = matrix[0].length - 1;
        
        while(row < matrix.length && col >= 0) {
            if(matrix[row][col] === target) {
                return true;
            } else if(matrix[row][col] > target) {
                col--;
            } else {
                row++;
            }
        }
        return false;
};

Code in Java:

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

Related

How to 10x Your LLM Prompting With DSPy

Tired of spending countless hours tweaking prompts for large...

Google Announces A Cost Effective Gemini Flash

At Google's I/O event, the company unveiled Gemini Flash,...

WordPress vs Strapi: Choosing the Right CMS for Your Needs

With the growing popularity of headless CMS solutions, developers...

JPA vs. JDBC: Comparing the two DB APIs

Introduction The eternal battle rages on between two warring database...

Meta Introduces V-JEPA

The V-JEPA model, proposed by Yann LeCun, is a...

Subscribe to our AI newsletter. Get the latest on news, models, open source and trends.
Don't worry, we won't spam. 😎

You have successfully subscribed to the newsletter

There was an error while trying to send your request. Please try again.

Lusera will use the information you provide on this form to be in touch with you and to provide updates and marketing.