Thursday 24 September 2015

Search in sorted matrix

Problem

Given a matrix whose rows and columns are sorted, search for an element in that matrix.

Solution

We start from the right top element of the array. If the search element is greater than the element we move  below, if it is less we move to the left. And we continue the above process In this way either we will find the element or will reach to a position  where no left or bottom is possible. In an N*M matrix the search complexity is O(N+M). In N*N matrix the complexity is O(2*N) = O(N)

Code

public class SearchInSortedMatrix
{
 public static void main(String[] args)
 {
  int[][] matrix =
  {
  { 5, 7, 8, 9 },
  { 6, 9, 11, 13 },
  { 7, 11, 12, 14 },
  { 8, 13, 16, 17 } };
  boolean result = contains(matrix, 14);
  System.out.println(result);

 }

 private static boolean contains(int[][] matrix, int k)
 {
  int row = matrix.length;
  int col = matrix[0].length;
  int currentRow = 0;
  int currentCol = col - 1;
  while (currentRow != row && currentCol != -1)
  {
   if (matrix[currentRow][currentCol] == k)
    return true;
   else if (matrix[currentRow][currentCol] > k)
    currentCol--;
   else
    currentRow++;
  }
  return false;
 }
}

No comments:

Post a Comment