Given a matrix containing unique numbers in which all rows and columns are in sorted order.
And You have to search an element output its location row,column number .
If no such element the just print ”-1 -1”.
And You have to search an element output its location row,column number .
If no such element the just print ”-1 -1”.
Example:
5 5 //size of matrix
-10 -5 -3 4 9 //matrix
-6 -2 0 5 10
-4 -1 1 6 12
2 3 7 8 13
100 120 130 140 150
-10 -5 -3 4 9 //matrix
-6 -2 0 5 10
-4 -1 1 6 12
2 3 7 8 13
100 120 130 140 150
3 // number of elements to be search
0 //element to be search
-2 //element to be search
170 //element to be search
0 //element to be search
-2 //element to be search
170 //element to be search
Output:
1 2 // location of 0
1 1 // location of -2
-1 -1 //location of 170
1 1 // location of -2
-1 -1 //location of 170
Solution:
We can use normal brute force solution which can give O(m*n) time complexity.
By using binary search we can further reduce the complexity by(m*log(n))
But here is the simplest and optimal solution which takes O(n+m) complexity which we can say if n=m then O(2n)=O(n) or similar order if n!=m
#include <iostream>
#include <stdio.h>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <limits.h>
#include <math.h>
using namespacestd;
int A[1009][1009];
int main()
{
int n,m;
scanf(“%d%d”,&n,&m);
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
scanf(“%d”,&A[i][j]);
}
}
int t;
cin>>t;
while(t–)
{
int p;
cin>>p;
int i=0,j=m–1;
bool f=false;
while(i<n && j>=0)
{
if(A[i][j]==p)
{
cout<<i<<” “<<j<<endl;
f=true;
break;
}
else if(A[i][j]>p)
{
j–;
}
else if(A[i][j]<p)
{
i++;
}
}
if(f==false) cout<<“-1 -1”<<endl;
}
return 0;
}
Article and code by Dheeraj