Search a sorted 2D Matrix

Companies:
  • Amazon Interview Questions
  • ByteDance Interview Questions
  • Facebook Interview Questions
  • Google Interview Questions
  • Microsoft Interview Questions
  • Walmart Labs Interview Questions

Problem Statement

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

  • Integers in each row are sorted in ascending from left to right.
  • Integers in each column are sorted in ascending from top to bottom.

Sample Test Cases

Consider the following matrix:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
Given target = 5, return true.
Given target = 20, return false.

Problem Solution

The idea is to use Divide and Conquer approach to solve this problem.

So what we can do is search for the particular row in the matrix using the Binary Search technique, between which our element ‘K’ which to be searched may lie ie. matrix[i][0]<=K<=matrix[i][n-1].

Then we apply Simple binary search on that particular row to find whether ‘K’ is present in that row or not.

Complexity Analysis

Time Complexity: The time complexity of this algorithm will be O(log m+log n) because first, we will search for the particular row using binary search in O(log n) and then search for the element in that particular row in O(log m).

Space Complexity: O(1) no extra space is required .

Code Implementation

#include <bits/stdc++.h>
using namespace std;

#define M 5
#define N 5

// Basic binary search to
// find an element in a 1-D array
bool binarySearch1D(int arr[], int K)
{
    int low = 0;
    int high = N - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;

        // if element found return true
        if (arr[mid] == K)
            return true;

        // if middle less than K then
        // skip the left part of the
        // array else skip the right part
        if (arr[mid] < K)
            low = mid + 1;
        else
            high = mid - 1;
    }

    // if not found return false
    return false;
}

// Function to search an element
// in a matrix based on
// Divide and conquer approach
bool searchMatrix(int matrix[M][N], int K)
{
    int low = 0;
    int high = M - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;

        // if the element lies in the range
        // of this row then call
        // 1-D binary search on this row
        if (K >= matrix[mid][0]
            && K <= matrix[mid][N - 1])
            return binarySearch1D(matrix[mid], K);

        // if the element is less then the
        // starting element of that row then
        // search in upper rows else search
        // in the lower rows
        if (K < matrix[mid][0])
            high = mid - 1;
        else
            low = mid + 1;
    }

    // if not found
    return false;
}

// Driver code
int main()
{
    int matrix[M][N] = {  {1,   4,  7, 11, 15},
  {2,   5,  8, 12, 19},
  {3,   6,  9, 16, 22},
  {10, 13, 14, 17, 24},
  {18, 21, 23, 26, 30} };
    int K = 3;
    if (searchMatrix(matrix, K))
        cout << "Found" << endl;
    else
        cout << "Not found" << endl;
}

 

Scroll to Top