Matrix Search que doubts

#1

help me solve below

Given an n x m matrix, where every row and column is sorted in increasing order, and a number x . Find if element x is present in the matrix or not.
Input Format

First line consists of two space separated integers N and M, denoting the number of element in a row and column respectively. Second line of each test case consists of N*M space separated integers denoting the elements in the matrix in row major order. Third line of each test case contains a single integer x, the element to be searched.
Constraints

1 <= N,M <= 30 0 <= A[i] <= 100
Output Format

Print 1 if the element is present in the matrix, else 0.
Sample Input

3 3
3 30 38
44 52 54
57 60 69
62

Sample Output

help me solve below

Explanation

Search the element in the sorted matrix. If the element is present print 1 otherwise print 0. In the sample input,in first case 62 is not present in the matrix so 0 is printed. Similarly, for second case 55 is present in the matrix so 1 is printed.

#2

hello @Kash-Moulik-3715574511847721
what doubt u have in this question?

#3

can u give a programm with efficient time and space complexity without using dp

#4

@Kash-Moulik-3715574511847721

logic - >
just go to each cell and check whether it is equal to target value or not.
another logic ->
Approach: The simple idea is to remove a row or column in each comparison until an element is found. Start searching from the top-right corner of the matrix. There are three possible cases.

  1. The given number is greater than the current number: This will ensure, that all the elements in the current row are smaller than the given number as the pointer is already at the right-most element and the row is sorted. Thus, the entire row gets eliminated and continue the search on the next row. Here elimination means that row needs not to be searched.
  2. The given number is smaller than the current number: This will ensure, that all the elements in the current column are greater than the given number. Thus, the entire column gets eliminated and continue the search on the previous column i.e. the column at the immediate left.
  3. The given number is equal to the current number: This will end the search
    pls refer this for clarity
    https://ide.codingblocks.com/s/372583
#5

yeah but ur code only pass 2/3 test case

#6

in line 10, replace n with m