Search In A 2D Matrix

Easy
0/40
Average time to solve is 10m
profile
Contributed by
179 upvotes
Asked in companies
HSBCAdobeCIS - Cyber Infrastructure

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 :
3 4 8
1 2 3 4
5 6 7 8
9 10 11 12
Sample Output 1 :
true
Explanation For Sample Input 1 :
The ‘target’  = 8 exists in the 'mat' at index (1, 3).
Sample Input 2 :
3 3 78
1 2 4 
6 7 8
9 10 34
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
Hint

Naively search the MAT to find the TARGET.

Approaches (2)
Brute Force

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

Time Complexity

O(M*N) where ‘M’ and ‘N’ denote the number of rows and columns in ‘MAT’, respectively.

 

In the worst case, we will be traversing the entire matrix of M*N elements.

Space Complexity

O(1)
 

Since, we are not using any extra space to find the number of pairs. Therefore, the overall space complexity will be O(1).

Code Solution
(100% EXP penalty)
Search In A 2D Matrix
Full screen
Console