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;
 }
 }
 System.out.println("Element is not found in sorted matrix");
 }
}

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

Element found at r =2 c=3

Don't miss the next article! 
Be the first to be notified when a new article or Kubernetes experiment is published.                            

 

 Share This

• Facebook

• Twitter

• Linkedin

• Pinterest