Matrix Search InterviewBit Solution

Problem: Matrix Search

Problem Description:

Given a matrix of integers A of size N x M and an integer B.

Write an efficient algorithm that searches for integer B in matrix A.

This matrix A has the following properties:

1. Integers in each row are sorted from left to right.

2. The first integer of each row is greater than or equal to the last integer of the previous row.

Return 1 if B is present in A, else return 0.

Note: Rows are numbered from top to bottom and columns are numbered from left to right.

Input Format

The first argument given is the integer matrix A.
The second argument given is the integer B.

Output Format

Return 1 if B is present in A, else return 0. 

Constraints

1 <= N, M <= 1000 
1 <= A[i][j], B <= 10^6 

For Example

Input 1:
    A = 
    [ [1,   3,  5,  7],
      [10, 11, 16, 20],
      [23, 30, 34, 50]  ]
    B = 3
Output 1:
    1

Input 2:
    A = [   [5, 17, 100, 111]
            [119, 120,  127,   131]    ]
    B = 3
Output 2:
    0

Approach

Since each row is sorted from left to right, and by the second condition we can conclude that columns are sorted from top to bottom as well.

We can use two binary search here, first binary search will find the row where element can be present, and second binary search will find the element in that row if present.

Time & Space Complexity

Time Complexity: O(log(M*N))

• Since the rows and columns are sorted, that means there can exist only one row which can contain our given element until and unless that element is the last element of that row, as the first element of the next row can be equal to last element of the current row.

But this condition doesn't bother us, as we only have to find only one row where the element can reside, if that row contains the element we return 1 otherwise 0.

So for the first binary search, time complexity would bhi O(logN), N being the number of rows. And for the second binary search time complexity would be O(logM), M being the number of columns, so overall time complexity is O(logM) + O(logN) = O(log(M*N)).

Space Complexity: O(1)

• We have not taken any other extra space, ignoring the space taken by the input array.

Solution:

Code in C++