Question Name:Search in a matrix

#include <bits/stdc++.h>

#define inp(x) scanf("%d",&x)
#define loop(i,n) for(ll i=0;i<n;++i)
#define pb push_back
#define mp make_pair
#define ll long long

using namespace std;
//-------------------------------------------------//

int main(){
    int t,m,n;
    cin >> t;

    while(t--){
        cin >> m >> n;
        int a[m][n];
        loop(i,m)
            loop(j,n)
                cin >> a[i][j];
        //Start at bottom left
        int key,x=m-1,y=0;
        cin >> key;
        
        while(x>=0 && y<n){
            if(a[x][y] == key){
                cout << 1 << endl;
                goto end;
            }
            (a[x][y] < key) ? (y++): (x--);
        }
        cout << 0 << endl;        
    end:;
    }
    return 0;
}

Problem Description

Given an n x m matrix, where every row and column is sorted in increasing order, and a number x .

The task is to find whether element x is present in the matrix or not.

Expected Time Complexity : O(m + n)

Input:
The first line of input contains a single integer T denoting the number of test cases. Then T test cases follow. Each test case consists of three lines.
First line of each test case consist 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.

Output:

Corresponding to each test case, print in a new line, 1 if the element x is present in the matrix, otherwise simply print 0.

Constraints:
1<=T<=200
1<=N,M<=30

  • Test Case 1

    Input (stdin)

    2
    3 3
    3 30 38 44 52 54 57 60 69
    62
    1 6
    18 21 27 38 55 67
    55
    

    Expected Output

    0
    1
  • Test Case 2

    Input (stdin)

    2
    3 2
    2 16 18 20 25 30
    60
    4 3
    2 30 49 56 57 64 20 10 34 54 63 72
    68
    
    

    Expected Output

    0
    0

Leave a Reply

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.