Search a 2D Matrix

Problem statement:

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

This question is from Leetcode.

Link to the question is:https://leetcode.com/explore/featured/card/october-leetcoding-challenge/561/week-3-october-15th-october-21st/3497/

Example:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 3
Output: true

Naive Approach:

We’ll traverse the array with two loops. One for row and another for column.Then we’ll check every element with the target value and check if it exists or not. If exists we’ll return true, else return false.

Implementation:

//c++//
bool searchMatrix(vector<vector<int>>& matrix, int target) {
 
 if(matrix.size()==0){
 return false;
 }
 
 for(int i = 0;i<matrix.size();i++){
 for(int j = 0;j<matrix.size();j++){
 if(matrix[i][j]==target){
 return true;
 }
 }
 }
 return false;
 
 }

Time Complexity:

So time complexity will be 0(n²) because we are taking two loops .

and space complexity is 0(1).

So it is not a better solution.

Efficient Solution:

Efficient solution will be not taking each row and column every time. We’ll start from rightmost element.

So take two integer i=0 and j=size of the matrix — 1

now we’ll check from matrix[i][j]. If the target value is greater than matrix[i][j] then it’ll be in the next row(as the array is sorted row and column wise).So we’ll increment i=i+1 and if the target value is less, then we’ll decrease j value. Finally if the target value is equal to matrix[i][j] then we’ll return true else false.

Code:

//c++//
bool searchMatrix(vector<vector<int>>& matrix, int target) {
    
        if(matrix.size()==0){
            return false;
        }
       
        int i=0, j=matrix[0].size()-1;
        while(i<matrix.size() && j>=0){
            if(matrix[i][j]==target){
                return true;
            }
            else if (target > matrix[i][j]){
                i++;
            }
            else{
                j--;
            }
        }
        return false;
        
    }

Time complexity:

As one traversal is required so time complexity is 0(n)

and space required is 0(1).