Search in a 2D Matrix

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.

Let's understand the problem

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:

  • 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.

Examples

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.

Discussed solution approaches

  • A brute force approach  using nested loops
  • An efficient approach  using binary search

A brute force approach using nested loops

A simple approach would be to traverse the whole matrix using nested loops and check whether the k is present or not.

Solution pseudocode

bool searchMatrix(int mat[][], int n, int m, int k) 
{
    for(int i = 0, i < n; i = i + 1)
    {
        for(j = 0; j < m; j = j + 1)
        { 
            if(mat[i][j] == k)
                return 1
        }
    }
    return -1
}

Solution analysis

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.

An efficient approach using binary search

Solution idea

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: 

  • Sorted in increasing order.
  • Greater than all the values in the (i - 1)th row.
  • Less than all the values in the (i + 1)th row.

Here is a solution idea using the above observation:

  • We first apply binary search on rows to find out the row in which k must lie, i.e., we need to find a row such that the first element of the row is greater than or equal to k and the last element of the row is less than or equal to k.
  • Then, we apply binary search in that row to find out if k is present in the matrix or not.

Solution pseudocode

bool searchMatrix(int mat[][], int n, int m, 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
}

Binary search implementation

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
}

Solution analysis

  • Time complexity = Time complexity of searching row where k is present + Time complexity of searching value k = O(logn) + O(logm) = O(log n + log m).
  • Space complexity = O(1). Think!

Critical ideas to think!

  • Suppose our matrix is just sorted in-row and column-wise but not strictly sorted i.e   the first integer of each row is not greater than the last integer of the previous row. Can we solve the problem using the above approach?
  • How do we modify the above code, if we need to return the index (i, j) of the value k, if k is present in the matrix?
  • Can we solve the above problem by searching the column and then searching elements in that column?
  • How can we implement the above approach using a recursive binary search? What would be the space complexity?

Comparisons of time and space complexities

  • Using nested loops: Time = O(nm), Space = O(1)
  • Using binary search: Time = O(logn + logm), Space = O(1)

Similar problems for practice

Thanks to Navtosh Kumar for his contribution in creating the first version of the content. Enjoy learning, Enjoy coding, Enjoy algorithms!

Share feedback with us

More blogs to explore

Our weekly newsletter

Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.

© 2022 Code Algorithms Pvt. Ltd.

All rights reserved.