# 2-clean-C++ implementation with detailed complexity analysis

• Here is the O(M+N) solution, It is important to make it clear we choose the position

``````     right-up-corner-position : can help us to exclude a column or a row
``````

So by judging the right-up-corner-value, we can exclude a column or a row one loop, so the loop is
O(M+N) time complexity.

``````class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m=matrix.size();
if(m==0)  return false;
int n=matrix[0].size();
/*** start from the right-up-position ***/
int i=0, j=n-1;
while(i<m && j>=0){
if(matrix[i][j]==target)  return true;
/*** the element-of-column-j >= matrix[i][j] > target ***/
else if(matrix[i][j]>target)  j--;
/*** the element-of-row-i <= matrix[i][j] < target ***/
else   i++;
}
return false;
}
};
``````

Here is a recursion-version-implementation, by analyzing the time complexity

``````  T(N)=3*(T(N/4)) + O(1)
``````

Based the master theory,

`````` f(n) = O(1) = O(log(4, 3-e))    with e=2
``````

So

`````` T(n) = O(N ^ log(4, 3) )    <  O(N)
``````

here is the C++ implementation:

``````   class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if(matrix.size()==0) return false;
int row=matrix.size(), col=matrix[0].size();
return help(matrix, 0, row-1, 0, col-1, target);
}

bool help(vector<vector<int>>& matrix, int row_start, int row_end, int col_start, int col_end, int target) {
if(row_start>row_end || col_start>col_end)  return false;
int row_mid=(row_start+row_end)/2, col_mid=(col_start+col_end)/2;
if(matrix[row_mid][col_mid]==target)    return true;
else if(matrix[row_mid][col_mid]>target){
/*** left-up || left-down || right-up ***/
return help(matrix, row_start, row_mid-1, col_start, col_mid-1, target) ||
help(matrix, row_mid, row_end, col_start, col_mid-1, target) ||
help(matrix, row_start, row_mid-1, col_mid, col_end, target);
}
else{
/*** right-down || left-down || right-up ***/
return help(matrix, row_mid+1, row_end, col_mid+1, col_end, target) ||
help(matrix, row_mid+1, row_end, col_start, col_mid, target) ||
help(matrix, row_start, row_mid, col_mid+1, col_end, target);
}
}
};``````

• Here is a recursion-version-implementation, by analyzing the time complexity

``````T(N)=3*(T(N/4)) + O(1)
``````

here is the C++ ...

Looks like you forgot the analysis.

• I have added the complexity analysis @StefanPochmann

• Rather bad. What is N?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.