Searching an element in the row and column wise sorted matrix is one of the basic proble of the matrix. It is one of those questions which are asked in technical interview .
Explaination : We can see that the number 8 is present in the last row and middle column. So here the index of the last row would be 2 and middle column would be 1, hence our output will be (2,1).
This problem can be solved in two ways :
1. Naive Solution : O(m*n)
2. Efficient Solutin : O(m+n)
where m is number of rows and n is number of columns.
Naive Solution : Java
class HindiCodingCommunity{
public static void search(int mat[][],int num)
{
for(int i=0;i<mat.length;i++)
{
for(int j=0;j<mat[i].length;j++)
{
if(mat[i][j]==num)
{
System.out.println("number found at ("+i+" "+j+")");
return;
}
}
}
System.out.println("number is not present");
}
public static void main(String args[])
{
int[][] mat= {{3,6,9},{4,7,10},{5,8,11}};
search(mat,8);
}
}
Time Complexity : O(m*n)
Efficient Solution : Java
class HindiCodingCommunity{
public static void search(int mat[][],int num)
{
int i=0;
int j= mat[0].length-1;
while(i<mat.length && j>=0)
{
if(mat[i][j]==num)
{
System.out.println("Number is found at "+i+" , "+j);
return;
}
else{
if(mat[i][j]>num)
j--;
else
i++;
}
}
System.out.println("Number is not found");
}
public static void main(String args[])
{
int[][] mat= {{3,6,9},{4,7,10},{5,8,11}};
search(mat,8);
}
}
Time Complexity : O(m+n)
