Last Updated: 11 Jan, 2021
Search a 2D Matrix II
Easy
Asked in companies
You are given a 2-D matrix of dimensions 'N' x 'M', each row of the matrix is sorted in non-decreasing order, and each column is sorted in non-decreasing order.
You are also given an integer ‘X’. You are supposed to find whether 'X' is present in the given matrix.
Input Format :
The first line contains three integers, ‘X’, ‘N’, and ‘M’, separated by a single space denoting the element to be searched, the number of rows in the matrix, and the number of columns in the matrix, respectively.
The next ‘N’ lines contain ‘M’ integers, each denoting the elements of the matrix.
Output Format :
Print “Yes”(without quotes) if ‘X’ is present in the matrix; otherwise, print “No”.
Note :
You don’t need to print anything; It has already been handled.
Constraints :
1 <= X <= 10^6
1 <= N,M <= 100
-10^6 <= ARR[i][j] <= 10^6
Where ARR[i][j] denotes the jth element of the i’th row of the given matrix.
Time Limit: 1 sec
Approaches
The idea is to iterate through the matrix and check if any element is equal to ‘X’.
The steps are as follows :
- Iterate from 0 to ‘N’, let’s say the current index is ‘i’, this will represent our current row.
- Iterate from 0 to ‘M’, let’s say the current index is ‘j’, this will represent the current column of the matrix.
- If arr[i][j] is equal to ‘X’ return true as we have found an element equal to ‘X’.
- Iterate from 0 to ‘M’, let’s say the current index is ‘j’, this will represent the current column of the matrix.
- If there is no element equal to ‘X’ return false.
The idea is to use the property of sorted rows of the matrix and apply binary search on each row.
The steps are as follows :
- Iterate from the 0 to ‘N’, let’s say the current index is ‘i’, this will represent our current row.
- Apply binary search on the current row,
- Initialize “low” to 0 and “high” to "M - 1", [low, high] will denote our search space.
- Now while low is less than or equal to high do the following,
- Assign a variable “mid” to (low + high) / 2.
- If arr[i][mid] is equal to ‘X’ then return true as we have found the element.
- If arr[i][mid] is greater than ‘X’ then change “high” to mid-1 because if ‘X’ is present in the current row then it will only be found at positions smaller than “mid”.
- Else change “low” to “mid+1” because if ‘X’ is present in the current row then it will only be found at positions greater than “mid”.
- If there is no element equal to ‘X’ return false.
The idea is to use the fact that each row is sorted and that each column is sorted. We will use the 2 pointer approach to solve the question.
The steps are as follows :
- Initially we will have two pointers, let’s say ‘i’ at 0 and another pointer, let’s say ‘j’ at “M - 1”.
- While the value of i is less than ‘N’ and the value of ‘j’ is non negative do the following steps :
- If arr[i][j] is equal to X, return true.
- If arr[i][j] is less than ‘X’ then increment the value of ‘i’ because ‘X’ will be greater than all values of i’th row(because each row is sorted), hence ‘X’ will never be found in the current row.
- If arr[i][j] is greater than ‘X’ then decrement the value of ‘j’, since all values in the j’th column will be greater than ‘X’(because each column is sorted), hence ‘X’ will never be found in the j’th column.
- If there is no element equal to ‘X’ return false.