Search a sorted matrix

Given a sorted matrix where rows and the columns are sorted. Write an algorithm to search an element in the matrix in O(n).


Please try solving this problem before jumping on the solution

Click to learn






Subscribe for more updates



Algorithm Visualization




Code Snippet

			
package com.ideserve.virendra.questions;

public class SortedMatrix {
	
public static boolean stairSearch(int matrix[][], int n, int element) {
  if (element < matrix[0][0] || element > matrix[n-1][n-1]) 
	  return false;
  int r = 0; // row
  int c = n-1;// column
  while (r <= n-1 && c >= 0) {
    if (matrix[r][c] < element) 
      r++;
    else if (matrix[r][c] > element)
      c--;
    else
      return true;
  }
  return false;
}

public static void main(String args[])
{
	int[][] mat =  {   { 2, 6, 7, 11},
					   { 3, 8, 10, 12},
					   { 4, 9, 11, 13},
					   { 5, 15, 16, 18}
					   };
	
	System.out.println(stairSearch(mat, 4, 9));
	
}

}
		

Order of the Algorithm

Time Complexity is O(n)
Space Complexity is O(1)


Contribution

  • Sincere thanks from IDeserve community to Virendra Karappa for compiling current post.


    Virendra Karappa