1.

Write a program in Java to search an element in a row-wise and column-wise sorted 2-D matrix of size M x N.

Answer»
You have to search the element in O(N + M) time complexity without using any extra space. Print “true” if the element exists in the matrix else print “false”.

The normal searching technique will take O(N2) time complexity as we will search every element in the matrix and see if it matches our target or not. The other approach uses the fact that the elements are sorted row-wise. We can apply binary search on every row. Hence, the time complexity will be O(Nlog2N)
Since we want the solution in O(N + M), this approach is not the one we will use. We will use the Staircase Search Algorithm. See, we know that the elements are sorted column-wise and row-wise. So, we start from the last element of the first row as shown below

Let us say we want to search for 21. We know that 21 is larger than 15. Since the matrix is row-wise sorted, element 15 is the largest element of this row. So, we are not going to find 21 in this row. So, we move directly to the last element of the next row. The Same is the case here as well. So, we move to the next row. Here, the element is 22. So, 21 might be present in this row. So, we move one step backwards in this row only.

On moving one step backwards, we see that we reach 16. Since this number is smaller than our target of 21, we know that we will not find our target in this row. Hence, we move to the last element of the next row and the same happens here too. Now, we are in the last row. We know that element might exist in this row. So, we keep on moving back in this row and find element 21.

So, we will implement this same algorithm. This is called staircase search. 

Java Code for Staircase Search

import java.util.*;
class Main {

public static boolean staircaseSearch(int[][] matrix, int target) {

if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;

int j = matrix[0].length - 1 ;
int i = 0;

while(i < matrix.length && j>=0) {
if(matrix[i][j] == target) return true;
else if(matrix[i][j] < target) {
i++;
} else {
j--;
}
}

return false;
}

public static void main(String args[]) {
// Your code goes here
Scanner scn = new Scanner(System.in);
int N = scn.nextInt();
int M = scn.nextInt();

int[][] mat = new int[N][M];

for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
mat[i][j] = scn.nextInt();
}
}

int target = scn.nextInt();

System.out.println(staircaseSearch(mat,target));
}
}

Sample Output

5 5
1  2  3  4  5
6  7  8  9  10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
21

Output: true


  • Time Complexity: O(N + M) is the time complexity of staircase search. This is because we will have to search for a maximum of one row and one column.


  • Auxiliary Space: O(1) as we have not used any extra space.


Discussion

No Comment Found

Related InterviewSolutions