# Search a 2D Matrix

• #### 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 a 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 in halves until a finding of 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 #2 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 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 current number consider all numbers on the left in the same `row` by moving the pointer to the left.

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.