Search In A 2D Matrix

Easy

0/40

Average time to solve is 10m

Contributed by

152 upvotes

Asked in companies

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.

Detailed explanation ( Input/output format, Notes, Images )

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?

Sample Input 1 :

Sample Output 1 :

true

Explanation For Sample Input 1 :

The ‘target’  = 8 exists in the 'mat' at index (1, 3).

Sample Input 2 :

Sample Output 2 :

false

Explanation For Sample Input 2 :

The ‘target' = 78 does not exist in the 'mat'. Therefore in the output, we see 'false'.

Constraints :

1 <= N <= 50
1 <= M <= 50
-10^5 <= mat[i], target <= 10^5

Time Limit: 1 sec

Console