# Solution by ananai

• #### Approach #1 Brute Force [Accepted]

Algorithm

Traverse the array comparing every element with the given target. Return `true` if the target was found return `false` after the completion of an iteration meaning that the target is not in a given array.

C++

``````bool searchMatrix(vector<vector<int>>& matrix, int target) {

for(int row = 0; row<matrix.size(); row++) {
for(int col = 0; col<matrix[row].size(); col++) {
if(matrix[row][col] == target) {
return true;
}
}
}

return false;
}
``````

Complexity Analysis

• Time complexity : \$\$O(mn)\$\$.

Because each of these nested loops executes `m` and `n` times respectively, the total time complexity is \$\$O(mn)\$\$, where `m` represents `rows` and `n` `columns`.

• Space complexity : \$\$O(1)\$\$.

#### Approach #2 Binary Search [Accepted]

Algorithm

The fact that every row of a given array is `sorted` make it possible to apply `binary search` for every row to search for the target value. Keep dividing a row into halves until finding the target value.

C++

``````bool searchMatrix(vector<vector<int>>& matrix, int target) {

for(int row = 0; row<matrix.size(); row++) {
int l = 0, r = (int)matrix[row].size()-1;
while(l<=r) {
int middle = l + (r - l)/2;
if(matrix[row][middle] == target) {
return true;
} else if(matrix[row][middle] < target) {
l = middle + 1;
} else {
r = middle - 1;
}
}
}

return false;
}
``````

Complexity Analysis

• Time complexity : \$\$O(mlogn)\$\$.

Iteration through rows in a given array takes `m` time where `binary search` on a row takes `logn` time, the total time complexity is \$\$O(mlogn)\$\$, where `m` represents `rows` and `n` `columns`.

• Space complexity : \$\$O(1)\$\$.

#### Approach #3 Pointer [Accepted]

Algorithm

The hint for this approach is the fact that

• 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.

Lets start the `pointer` at last column of the first row meaning that `all numbers below current number are greater than current number and all numbers left to current number are less than current number`. Comparing current number with target number it can be decided in which direction to move the pointer. If current number is equal to a target number this means that target value was found then stop the pointer. If current number is less than target number then consider numbers below so move the pointer to next `row`; otherwise, if current number is greater than target number consider all numbers on the left in the same `row` by moving the pointer to the left.

Lets find `11` in the following example

C++

``````bool searchMatrix(vector<vector<int>>& matrix, int target) {

if(matrix.size() == 0) {
return false;
}

int m = (int)matrix.size();
int n = (int)matrix[0].size();

int row = 0, col = n-1;

while(row<m && col>=0) {
if(matrix[row][col] == target) {
return true;
} else if(matrix[row][col]>target) {
col--;
} else {
row++;
}
}

return false;
}
``````

Complexity Analysis

• Time complexity : \$\$O(m+n)\$\$.

Iteration through rows in a given array takes `m` time and iteration through columns takes `n` time. The fact that the pointer can only move down or left makes the total time complexity \$\$O(m+n)\$\$, where `m` represents `rows` and `n` `columns`.

• Space complexity : \$\$O(1)\$\$.

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