Checkout your overall progress in every topic here
in DSA topics
Open the topic and solve more problems associated with it to improve your skills
Check out the skill meter for every topic
See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.
Search In A 2D Matrix
Avg time to solve 10 mins
Success Rate 90 %
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 exists).
You are given an integer 'TARGET' and your task is to find if it exists in the given 'MAT' or not.
Given Matrix : 1 1 and Target : 8
The output should be "TRUE" as 8 is present in the Matrix.
Detailed explanation ( Input/output format, Notes, Constraints, Images )
Input Format :
The first line of input contains an integer 'T' representing the number of test cases Then the test case follows :
The first line of each test case 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 of each test case, the next 'N' lines represent the rows of the 'MAT'. Every row contains 'M' single space-separated integers.
Output Format :
For each test case, print “TRUE” if 'TARGET' is present in the 'MAT', else print “FALSE”.
You do not need to print anything, it has already been taken care of. Just implement the function.
1 <= T <= 10^2
1 <= N <= 50
1 <= M <= 50
-10^5 <= MAT[i], TARGET <= 10^5
Time Limit : 1 sec
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 :
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
2 2 8
Sample Output 2 :
Explanation For Sample Input 2 :
The 'TARGET' = 78 do not exists in the 'MAT'.
The 'TARGET' = 8 exists in the 'MAT' at index (1, 1).