Difficulty: Easy, Asked-in: Microsoft, Amazon, Adobe, Directi, Goldman Sachs, Paytm, SAP, Visa
Key takeaway: An excellent problem to learn problem-solving using the binary search.
You are given a row-wise and column-wise sorted 2D matrix and an integer k, write a program to find whether the integer k is present in the matrix or not. The matrix has the following properties:
Input: k = 6
mat[][] =
[
[1, 2, 6, 7],
[12, 13, 16, 21],
[23, 35, 36, 48]
]
Output: true
Explanation: value 6 is present in the matrix.
Input: k = 7
mat[][] =
[
[1, 2, 6],
[12, 13, 16],
[23, 35, 36]
]
Output: fasle
Explanation: value 7 is not present in the matrix.
A simple approach would be to traverse the whole matrix using nested loops and check whether the k is present or not.
bool searchMatrix(int mat[][], int m, int n, int k)
{
for(int i = 0, i < m; i = i + 1)
{
for(j = 0; j < n; j = j + 1)
{
if(mat[i][j] == k)
return true
}
}
return false
}
Note: Here m is number of rows and n is number of columns.
def searchMatrix(mat, m, n, k):
for i in range(n):
for j in range(m):
if mat[i][j] == k:
return True
return False
We are using two nested loops, where the outer loop selects the row, and the inner loop keeps track of the column. So time complexity = O(n*m), Here n is the number of rows, and m is the number of columns. Space Complexity = O(1), we are not using any additional space.
Now the critical question is: How can we improve the time complexity? Can we use the sorted order property to solve it efficiently? Let's think!
Here each matrix row is sorted i.e. the first element of a row is greater than or equal to the last number of the preceding row. Therefore, the matrix can be viewed as a sorted one-dimensional array (both row-wise and column-wise sorted). Can we apply the idea of binary search? Let's think!
If we pick any ith row then all the values in the ith row would be:
Here is a solution idea using the above observation:
bool searchMatrix(int mat[][], int m, int n, int k)
{
int l = 0, r = m - 1
while (l <= r)
{
int mid = l + (r - l) / 2
if (k >= mat[mid][0] && k <= mat[mid][n-1])
return searchRow(mat[mid], n, k)
if (k < mat[mid][0])
r = mid - 1
else
l = mid + 1
}
return false
}
bool searchRow(int M[], int n, int k)
{
int l = 0, r = n - 1
while (l <= r)
{
int mid = l + (r - l) / 2
if (M[mid] == k)
return true
if (k < M[mid])
r = mid - 1
else
l = mid + 1
}
return false
}
def searchRow(M, n, k):
l, r = 0, n - 1
while l <= r:
mid = l + (r - l) // 2
if M[mid] == k:
return True
elif k < M[mid]:
r = mid - 1
else:
l = mid + 1
return False
def searchMatrix(mat, m, n, k):
l, r = 0, m - 1
while l <= r:
mid = l + (r - l) // 2
if k >= mat[mid][0] and k <= mat[mid][n - 1]:
return searchRow(mat[mid], n, k)
elif k < mat[mid][0]:
r = mid - 1
else:
l = mid + 1
return False
Enjoy learning, Enjoy coding, Enjoy algorithms!
Subscribe to get well designed content on data structure and algorithms, machine learning, system design, object orientd programming and math.
©2023 Code Algorithms Pvt. Ltd.
All rights reserved.