Example 1: Input: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 3 Output: true
This problem can be solved in 2 ways.
- By eliminating one row or column at a time.
- By binary search.
1. By eliminating one row or column at a time.
We start from top right corner (matrix[0][n-1]) and check if the “target” is greater than matrix[0][n-1] remove the row, else if the “target” is lesser than matrix[0][n-1], then remove the column.
Let us analyze by taking an example:
matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 3
Pass 1: m = 0 n = 3 if(target == matrix[0][3]) => false; if(target > matrix [0][3] ) ? => if (3 > 7) false if(target < matrix [0][3] ) ? => if (3 < 7) true remove last column. n --
Pass 2: m = 0 n = 2 if(target == matrix[0][2]) => false; if(target > matrix [0][2] ) ? => if (3 > 5) false if(target < matrix [0][2] ) ? => if (3 < 5) true remove last column. n --
Pass 3: m = 0 n = 1 if(target == matrix[0][1]) => true; Hence the result is true.
2. By binary search.
If you observe the matrix carefully, it can be treated as a sorted array. Hence we can apply binary search to search the “target”.
Below is the formula we use to convert a matrix to an array and vice-versa.
To convert a matrix into an array => matrix[x][y] => a[x * m + y] To convert an array into a matrix => a[x] =>matrix[x / m][x % m];
Solution in C++
#include<iostream> #include<vector> using namespace std; bool search_matrix_eliminating_row_column(vector<vector<int> > &matrix, int target) { int row_length = matrix.size(); int column_length = matrix[0].size(); //edge case if (target < matrix[0][0] || target > matrix[row_length - 1][column_length - 1]) return false; int row = 0; int column = column_length-1; while(row >=0 && row < row_length && column >= 0 && column<column_length) { if(target == matrix[row][column]) return true; else if(target > matrix[row][column]) row++; else if(target < matrix[row][column]) column--; } return false; } bool search_matrix_binary_search(vector<vector<int> > &matrix, int target) { int row = matrix.size(); int column = matrix[0].size(); //edge case if (target < matrix[0][0] || target > matrix[row - 1][column - 1]) return false; //get the length for the array. int left = 0; int right = row * column - 1; while (right > left) { int mid = left + (right - left) / 2; if (matrix[mid/column][mid%column] < target) { left = mid + 1; } else { right = mid; } } return matrix[right/column][right%column] == target; } int main() { //Initialize 2D vector vector<vector<int> > matrix = { { 1, 3, 5, 7 }, { 10, 11, 16, 20 }, { 23, 30, 34, 50 }, }; int target = 3; //bool result = search_matrix_eliminating_row_column(matrix, target); bool result = search_matrix_binary_search(matrix, target); if(result) { cout<<"The target is present in the matrix"<<endl; } else { cout<<"The target is NOT present in the matrix"<<endl; } return 0; }
Output:
The target is present in the matrix