## Search a 2-D Matrix Difficulty: Medium

#### 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

1. Linear traversal: Traverse throughout the matrix, while comparing each element with the target
2. Remove row col in each comparison: Starting from the top right of matrix, move towards the bottom left in search of the target element.
3. 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

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

Pseudo Code

``````bool searchMatrix(int[][] matrix, int target) {
if(matrix.empty())
return false
int n = matrix.size()
int m = matrix.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`

1. if `matrix[row][col]` is equal target, return true.
2. 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’.
3. 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.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.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!