Leetcode 74: Search an element in 2D sorted matrix

techieindoor

2 years ago

Here, we will learn how to search an element in 2D sorted matrix by code and algorithm. We will solve it by using binary search.

You have to write an efficient algorithm that searches for a given value in an m * 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:

1	6	9	10
11	12	16	20
23	30	40	60

Matrix: [[1, 6, 9, 10], [11, 12, 16,20], [23, 30, 40,60]] , Target: 9
Output: true

Explanation: 9 is present in matrix at 0th row and 2nd column i.e matrix[0][2]

Example 2:

1	3	4	9
10	11	16	21
24	30	34	60
65	70	75	80

Matrix: [[1,3,4,9],[10,11,16,21],[24,30,34,60],[65,70,75,80]]
Target: 15

Output: false

Explanation: 15 is not present in matrix.

How to get row and column from index in matrix:

row_index = index / column_size
column_index. = index % column_size

Algorithm:

Find the start point of matrix
Find the end point of matrix i.e (m * n)
Use binary search
- If value at middle index of matrix is equal to target then return true
- If value at middle index of matrix is less than target then update start point by mid + 1
- If value at middle index of matrix is greater than target then update end point by mid – 1

*** There are multiple ways to solve this problem

C++ code to search an element in sorted 2D matrix.

Code 1:

#include <iostream>
#include <vector>

using namespace std;

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int row = matrix.size();
    int col = matrix[0].size();
        
    int start = 0, end = (row * col) - 1;
        
    while(start <= end) {
        int mid = (start + end) / 2;
            
        int tmp_row = mid / col;
        int tmp_col = mid % col;
            
        if(matrix[tmp_row][tmp_col] == target) {
            return true;
        } else if(matrix[tmp_row][tmp_col] < target) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return false;
}

int main()
{
    vector<vector<int>> matrix = {
        {1, 6, 9, 10},
        {11, 12, 16, 20},
        {23, 30, 40, 60}
    };
    
    int target = 9;
    
    cout<<searchMatrix(matrix, target);
    
    return 0;
}

Output: true

Time complexity: O(log (m*n))
Space complexity: O(1) >>> There is no extra memory being used.

Code 2:

#include <iostream>
#include <vector>

using namespace std;

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int m = matrix.size();
    int n = matrix[0].size();
        
    int i = m-1;
    int j = 0;

    while (i >= 0 && j < n) {
        if (matrix[i][j] == target)
            return true;
        if (matrix[i][j] < target)
            j++;
        else
            i--;
    }
    return false;
}

int main()
{
    vector<vector<int>> matrix = {
        {1, 6, 9, 10},
        {11, 12, 16, 20},
        {23, 30, 40, 60}
    };
    
    int target = 9;
    
    cout<<searchMatrix(matrix, target);
    
    return 0;
}

Output: true

Code 3:

#include <iostream>
#include <vector>

using namespace std;

bool search_ele(vector<int> arr, int i, int n, int target) {
    while(i <= n) {
        int mid = (i+n) / 2;
            
        if(arr[mid] == target) {
            return true;
        }
        if(arr[mid] < target) {
            i = mid + 1;
        } else {
            n = mid - 1;
        }
    }
    return false;
}
bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int size = matrix.size();
        
    for(int i = 0; i  < size; i++) {
        int col_size = matrix[i].size();
        if(matrix[i][0] < target && matrix[i][col_size-1] < target) {
            continue;
        } else {
            return search_ele(matrix[i], 0, col_size-1, target);
        }
    }
    return false;
}

int main()
{
    vector<vector<int>> matrix = {
        {1, 6, 9, 10},
        {11, 12, 16, 20},
        {23, 30, 40, 60}
    };
    
    int target = 100;
    
    cout<<searchMatrix(matrix, target);
    
    return 0;
}

Output: false

To check more leetcode problem’s solution. Pls click given below link:

https://www.techieindoor.com/category/leetcode/