## Search a 2-D Matrix

**Difficulty: **Medium

**Asked in: **Amazon, Microsoft

#### Understanding The Problem

**Problem Description**

You are given a matrix `arr`

of m x n size. Write a program to search for a value `k`

in `arr`

. This `arr`

has the following properties:

- Integers in each row are sorted from left to right.
- The first value of each row is greater than the last value of the previous row.

If the value is found, then return 1 otherwise return 0.**Example 1**

```
Input:
arr[][] = [
[23, 25, 35, 37],
[40, 41, 42, 43],
[50, 60, 74, 80]
]
k = 41
Output: 1
Explanation: The value 41 is present in the array arr. So, 1 is returned.
```

**Example 2**

```
Input:
arr[][] = [
[23, 25, 35, 37],
[40, 41, 42, 43],
[50, 60, 74, 80]
]
k = 100
Output: 0
Explanation: The value 100 is not present in the array arr. So, 0 is returned.
```

#### Solutions

We will be discussing various solutions for the problem

**Linear traversal**: Traverse throughout the matrix, while comparing each element with the target**Remove row col in each comparison**: Starting from the top right of matrix, move towards the bottom left in search of the target element.**Binary Search**: Considering the matrix as a single array, perform a binary search for the target.

You may try this problem here.

#### 1. Linear Search

The simple idea is to traverse the array and to compare the target element with all the elements in the matrix one by one.

**Solution Step**

- Run a nested loop, outer loop for row and inner loop for the column
- Check every element with target and if the element is found then return True
- If the element is not found, then return False.

**Pseudo Code**

```
bool searchMatrix(int[][] matrix, int target) {
if(matrix.empty())
return false
int n = matrix.size()
int m = matrix[0].size()
for(int i = 0 to i < m) {
for(int j = 0 to j < n)
//if the element is found
if(mat[i][j] == target) {
return true
}
}
return false
}
```

**Complexity Analysis**

Time Complexity: O(m*n)

Space Complexity: O(1)

**Critical Ideas To Think**

- Did we use the sorted rows characteristic of the input matrix to search the target element?
- Can you think of a better approach in terms of time complexity?

#### 2. Remove row col in each comparison

Start from the top right corner: `row = 0, col = m-1`

- if
`matrix[row][col]`

is equal target, return true. - if
`matrix[row][col]`

is less than the target,`row = row + 1;`

indicates that this row can’t contain the target because this one in this line is the biggest one, counting from ‘row’. - if
`matrix[row][col]`

is greater than the target,`col = col — 1`

; indicate that this column can’t contain the target because this one in this column is the smallest one, counting from ‘col’.

**Pseudo Code**

```
bool searchMatrix(int[][] matrix, int target) {
if(matrix.empty())
return false
int n = matrix.size()
int m=matrix[0].size()
int row = 0,col = m-1
while(row < n and col >= 0){
if(matrix[row][col] == target)
return true
else if(matrix[row][col] < target)
row = row + 1
else
col = col - 1
}
return false
}
```

**Complexity Analysis**

Time Complexity: O(m + n)

Space Complexity: O(1)

**Critical Ideas To Think**

- Why did we increment row when
`matrix[row][col] < target`

? - How we are reducing our problem space on each comparison?
- Try this algorithm by dry running over some examples.

#### 3. Binary Search

The problem statement states that the values of the last col of the `ith`

row is greater than the first col of `(i+1)th`

row. Also, each row is sorted.

This means that, if will linearly arrange the elements of each row, we will have a sorted array. So we can now perform a binary search over it.

**How will the matrix behave like an array without actually creating an auxiliary array?**

It could be achieved by the following formula →

A `n * m`

matrix converted into an array: matrix[x][y] → a[x * m + y]

An array can be converted into `n * m`

matrix: a[x] → matrix[x / m][x % m]

**Solution Steps**

- Operate the matrix as an array using the above formula
- Perform a binary search for the target element over the matrix

**Pseudo Code**

```
bool searchMatrix(int[][] matrix, int target) {
int n = matrix.size()
int m = matrix[0].size()
int l = 0, r = m * n - 1
while (l != r){
mid = (l + r - 1) / 2
if (matrix[mid / m][mid % m] < target)
l = mid + 1
else
r = mid
}
if( matrix[r / m][r % m] == target )
return true
else
return false
}
```

**Complexity Analysis**

Time Complexity: O(log(m*n)) = O(log(m) + log(n))

Space Complexity: O(1)

**Critical Ideas To Think**

- Why did we initialize
`r`

with`m*n -1`

? - What will be the mid position of l and r in the matrix?
- How did we convert the array index into the matrix index and matrix index into the array index?

#### Comparison Of Solutions

#### Suggested Problems To Solve

- Search in a row-wise and column-wise sorted matrix
- Check if a grid can become row-wise and column-wise sorted after adjacent swaps
- Print all elements in sorted order from the row and column-wise sorted matrix
- Sort the matrix row-wise and column-wise

If you have any more approaches or you find an error/bug in the above solutions, please comment down below.

**Happy Coding!**

**Enjoy Algorithms!**