Problem

Submissions

Hints & solutions

Discuss

Search in a 2D matrix

Easy

0/40

Contributed by

19 upvotes

Asked in companies

Problem statement

You are given a 2-D matrix with 'N' rows and 'M' columns, each row of the matrix is sorted in non-decreasing order and the first element of each row is greater than or equal to the last element of the previous row. You are also given an integer ‘X’, you are supposed to find whether 'X' is present in the given matrix or not.

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

Input Format :

The first line contains a single integer ‘T’ denoting the number of test cases. The test cases are as follows.

The first line of each test case contains three integers ‘X’, ‘N’ and ‘M’ separated by a single space denoting the element to be searched, the number of rows in the matrix, and the number of columns in the matrix respectively.

The next ‘N’ lines contain ‘M’ integers each denoting the elements of the matrix.

Output Format :

For each test case, print “Yes”(without quotes) if ‘X’ is present in the matrix otherwise print “No”.

Print the output of each test case on a new line.

Note :

You don’t need to print anything; It has already been taken care of.

Constraints :

1 <= T <= 50
1 <= X <= 10 ^ 6
1 <= N, M <= 100
-10 ^ 6 <= ARR[i][j] <= 10 ^ 6

Where ‘T’ denotes the number of test cases, ‘N’ denotes the number of rows in a matrix, ‘M’ denotes the number of columns in the matrix and ARR[i][j] denotes the j-th element of the i’th row of the given matrix.

Time Limit: 1 sec

Sample Input 1 :

2
4 2 2
2 4
8 12
7 3 4
1 2 4 5
8 12 14 16
23 25 26 29

Sample Output 1 :

Yes
No

Explanation of Sample Input 1 :

In the first test case, the 2nd element of the first row is equal to 4, hence the output is “Yes”.

In the second test case, 7 is not present in the matrix hence the output is “No”.

Sample Input 2 :

Sample Output 2 :

Yes
No

Explanation of Sample Input 2 :

In the first test case, the only element is equal to 2, hence the output is “Yes”.

In the second test case, 22 is not present in the matrix hence the output is “No”.

Hint 1

Hint 2

Hint 3

Can you try to iterate through the matrix?

Approaches (3)

Approach 1

Approach 2

Approach 3

Brute force Approach

The idea is to iterate through the matrix and check if any element is equal to ‘X’.

The steps are as follows :

Iterate from 0 to ‘N’, let’s say the current index is ‘i’, this will represent our current row.
1. Iterate from 0 to ‘M’, let’s say the current index is ‘j’, this will represent the current column of the matrix.
  1. If arr[i][j] is equal to ‘X’ return true as we have found an element equal to ‘X’.
If there is no element equal to ‘X’ return false.

Time Complexity

O(N*M), where ‘N’ is the number of rows and ‘M’ is the number of columns in the matrix.

We are iterating through the matrix which has ‘N’ rows and each row has ‘M’ elements, thus the total elements are N*M. Thus, the overall time complexity is O(N*M).

Space Complexity

O(1).

We are using constant space. Thus, the overall space complexity is O(1).

(100% EXP penalty)

Search in a 2D matrix

Console