Search in a 2D Matrix

Difficulty: Easy, Asked-in: Microsoft, Amazon, Adobe, Directi, Goldman Sachs, 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.
• Suppose all matrix values are unique.

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

• Brute force approach  using nested loops
• Efficient approach  using binary search

Brute force approach using nested loops

A simple approach would be to traverse the whole matrix using nested loops and check whether k is present or not. If value k is present, then return true. Otherwise, if by the end of the nested loop, k is not present, then return false.

Solution code C++

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

Note: Here m is number of rows and n is number of columns.

Solution code Python

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

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). Space complexity = O(1), since we are using constant memory.

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. So, we can visualize the matrix as a list of sorted one-dimensional arrays. 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.

So we can first apply binary search on the 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 search for k.

Solution pseudocode

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;
}

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;
}

Python implementation

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

Solution analysis

Time complexity = Time complexity of binary search to find row where k is present + Time complexity of binary search to find k in that row = O(logm) + O(logn) = O(log m + log n). We are using constant extra space and iterative binary search, so space complexity = O(1).

Critical ideas to think!

• If our matrix is sorted row-wise and column-wise, but not strictly sorted (i.e., the first integer of each row is not necessarily greater than the last integer of the previous row), can we still solve the problem using the approach mentioned above?
• How can we modify the code to return the indices (i, j) of the value k if it is present in the matrix?
• Is it possible to solve the problem by first searching the column and then searching for elements in that column?
• How can we implement the above approach using recursive binary search, and what would be the associated space complexity?

Comparisons of time and space complexities

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

Similar problems for practice

• Search in a row-wise sorted 2D matrix
• Median of two sorted arrays
• Binary search algorithm
• Find the first and last position of an element in a sorted array
• Find the row with the maximum number of 1s
• Max in an array which is first increasing and then decreasing

Enjoy learning, Enjoy coding, Enjoy algorithms!