Search a 2D Matrix II

Easy
0/40
Average time to solve is 15m
profile
Contributed by
35 upvotes
Asked in companies
SalesforceAmazonFlipkart limited

Problem statement

You are given a 2-D matrix of dimensions 'N' x 'M', each row of the matrix is sorted in non-decreasing order, and each column is sorted in non-decreasing order.


You are also given an integer ‘X’. You are supposed to find whether 'X' is present in the given matrix.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line 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 : 
Print “Yes”(without quotes) if ‘X’ is present in the matrix; otherwise, print “No”.
Note : 
You don’t need to print anything; It has already been handled.
Constraints : 
1 <= X <= 10^6
1 <= N,M <= 100
-10^6 <= ARR[i][j] <= 10^6

Where ARR[i][j] denotes the jth element of the i’th row of the given matrix.

Time Limit: 1 sec
Sample Input 1 :
8 3 4
1 2 4 5
3 4 9 16
7 10 14 29
Sample Output 1 :
No
Explanation For Sample Input 1 :
8 is absent in the matrix; hence the output is “No”.
Sample Input 2 :
5 3 3
1 2 3
4 5 6
7 8 9
Sample Output 2 :
Yes
Hint

Can you try to iterate through the matrix?

Approaches (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.
    • Iterate from 0 to ‘M’, let’s say the current index is ‘j’, this will represent the current column of the matrix.
      • 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).

Code Solution
(100% EXP penalty)
Search a 2D Matrix II
Full screen
Console