Last Updated: 14 Dec, 2020

Search In A 2D Matrix

Easy

Asked in companies

Solve now

Problem statement

You have been given a 2-D array 'mat' of size 'M x N' where 'M' and 'N' denote the number of rows and columns, respectively. The elements of each row are sorted in non-decreasing order.

Moreover, the first element of a row is greater than the last element of the previous row (if it exists).

You are given an integer ‘target’, and your task is to find if it exists in the given 'mat' or not.

Example:

Input: ‘M’ = 3, 'N' = 4, ‘mat’ = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]], ‘target’ = 8

Output: true

Explanation: The output should be true as '8' exists in the matrix.

Input Format :

The first line contains three space-separated integers 'M', 'N', and ‘target’ where 'M' and 'N' denote the number of rows and columns of the 'mat', respectively, and ‘target’ is the integer to be found.

From the second line, the next 'M' lines represent the rows of the 'mat'. Every row contains 'N' single space-separated integers.

Output Format :

Return 'true' if ‘target’ is present in the 'mat'; else, return 'false'.

Note :

You do not need to print anything. It has already been taken care of. Just implement the function.

Follow-Up:

Can you solve this problem in less than O(M*N) time complexity?

Solve now

Approaches

01 Approach

We have a brute force solution to this problem. We can simply traverse the matrix and check if ‘TARGET’ exists or not.

Solve now

02 Approach

Since every row of the given matrix is sorted and the first element of row ‘i’ is greater than the last element of row ‘i-1’ (if exist), all the M*N elements of the matrix are arranged in an ascending order.

The intuition behind this approach is that since we can map indices of a matrix to an array, we can treat the given matrix as an array/list of M*N sorted integers.

We map the indices of matrix elements to a 1D array as follows :

If we copy the elements of a matrix (say ‘MAT’) to an array (say ‘ARR’) in a row-wise manner, then the element ‘MAT[i][j]' is equal to ‘ARR[N*i+j]’, where ‘N’ denotes the number of columns in ‘MAT’.
Similarly, converting ‘ARR’ back to ‘MAT’, the element ‘ARR[i]’ is equal to ‘MAT[i/N][i%N]’ as ‘ARR’ contains M*N elements, so ‘rowNum’ is equal to i/N and ‘colNum' is equal to i%N.

Now, we simply use binary search to find the ‘TARGET’.

Solve now