Wednesday, May 4, 2022

Question 36 : Search in a row wise and column wise sorted matrix.

Given row wise and column wise sorted matrix ,we need to search element with minimum time complexity.

Solution :

Solution 1:

You can simply search an element in 2D matrix but it will be done in O(R*C) complexity.

Solution 2:

• Iterate over each row
• Do binary search on rows unless you find the element.
• If you do not find the element , return false.

Time complexity : O(C*logR)

Solution 3:

We will use below logic to search an element

• Elements right to current element will be greater than element
• Elements left to current element will be lesser than element
• Elements down to current element will be greater than element
• Elements top to current element will be lesser than element
Algorithm:
• Starts with top right element, so initialise r=0 and c=
sortedMatrix[0].length-1
• Iterate over matrix with boundary conditions.
• If current element lets say m is equal to element X, return it.
• If m < X, go left,so decrease column by 1 (c--).
• If m > X, go right, so increase row by 1(r++).
Time complexity : O(R+C)

Java program to Search in a row wise and column wise sorted matrix:

``````public class SearchElementInSortedMatrixMain {

public static void main(String[] args) {
int[][] sortedMatrix =
{
{ 1, 6, 10, 12, 20 },
{ 4, 8, 15, 22, 25 },
{ 5, 20, 35, 37, 40 },
{ 10, 28, 38, 45, 55 }
};

searchElementInSortedMatrix(sortedMatrix, 37);
}

private static void searchElementInSortedMatrix(int[][] sortedMatrix, int X) {
int R = sortedMatrix.length;
int C = sortedMatrix[0].length;
int r = 0, c = C - 1;

// We can go either left or down
// left => decrement in columns, 0 will be the bound
// down => increment in row, R-1 will be the bound
while (r <= R - 1 && c >= 0) {
if (sortedMatrix[r][c] == X) {
// Found the element
System.out.println("Element found at r =" + r + " c=" + c);
return;
}
if (X < sortedMatrix[r][c]) {
// move left
c = c - 1;
} else {
// move down
r = r + 1;
}
}
}
}``````

When you run the program, you will get below output:

``Element found at r =2 c=3``

You may also like

Kubernetes Microservices
Python AI/ML
Spring Framework Spring Boot
Core Java Java Coding Question
Maven AWS