Find element in a sorted matrix

This is one of my favorite interview question. Suppose there is m*n matrix, where every row and column is sorted in increasing order. Given a number x, find whether x is in the matrix or not.

It is good to take an example first.

10 13 20 35 46

11 15 25 38 49

15 17 27 41 51

20 23 31 45 53

First try to understand the problem; elements are sorted in ascending order. You can use this scenario, while solving the problem.

To solve this problem, you can start at upper right corner (or) lower left corner.

I am going to explain using upper right corner approach; you try using lower left corner.

Suppose, you want to search for element 23.

Upper right corner element is 46.

Step 1: Compare 23 with 46.

 23 < 46 Here we need to take decision to travel left (or) down. Since elements are in sorted order, 23 definitely not below 46, so we have to travel left.

Step 2: Compare 23 with 35.

         23 < 35 Again we have to travel left

Step 3: Compare 23 with 20

         23 < 20 false, so we have to travel down.

Step 4: 23 < 25 (true), we have to travel left.

Step 5: 23 < 15 false, we have to travel down.

Step 6: 23 < 17, false, we have to travel down

Step 7: 23=23 stop procedure, since we find element.

 Lets try to formulate algorithm.

A is a matrix of size m * n. x is the element to find.

row = 0, col = n-1

Step 1: e = a[row][col] (Upper left corner element)

        

Step 2: If (e == x) return true;

Step 3:

if ( x < e) {

col = col-1

}else{

         row = row + 1

}

if(col == -1 || row == m) return false;

Repeat steps 1, 2 and 3 until you find elements.

import java.util.Objects;

public class SearchMatrix {
 private int matrix[][];
 private int rows, cols;

 public int[][] getMatrix() {
  return matrix;
 }

 public void setMatrix(int[][] matrix) {
  if (Objects.isNull(matrix)) {
   throw new NullPointerException("Matrix shouldn't be null");
  }
  this.matrix = matrix;
  rows = matrix.length;
  cols = matrix[rows - 1].length;
 }

 public boolean findElement(int x) {
  if (getMatrix() == null)
   throw new NullPointerException("Matrix is not initialized");
  int tempRow = 0, tempCol = cols - 1;
  int element;

  do {
   element = matrix[tempRow][tempCol];
   if (element == x)
    return true;
   else if (element > x)
    tempCol--;
   else
    tempRow++;
  } while (tempCol != -1 && tempRow != rows);

  return false;

 }

}

Following are the junit test cases.

import static org.junit.Assert.*;

import org.junit.Test;

public class SearchMatrixTest {

 @Test
 public void test1() {
  SearchMatrix searchMatrix = new SearchMatrix();
  int matrix[][] = { { 10, 13, 20, 35, 46 }, { 11, 15, 25, 38, 49 },
    { 15, 17, 27, 41, 51 }, { 20, 23, 31, 45, 53 } };
  searchMatrix.setMatrix(matrix);

  searchMatrix.setMatrix(matrix);

  assertTrue(searchMatrix.findElement(10));
  assertTrue(searchMatrix.findElement(13));
  assertTrue(searchMatrix.findElement(20));
  assertTrue(searchMatrix.findElement(35));
  assertTrue(searchMatrix.findElement(46));
  assertTrue(searchMatrix.findElement(11));
  assertTrue(searchMatrix.findElement(15));
  assertTrue(searchMatrix.findElement(25));
  assertTrue(searchMatrix.findElement(38));
  assertTrue(searchMatrix.findElement(49));
  assertTrue(searchMatrix.findElement(15));
  assertTrue(searchMatrix.findElement(17));
  assertTrue(searchMatrix.findElement(27));
  assertTrue(searchMatrix.findElement(41));
  assertTrue(searchMatrix.findElement(51));
  assertTrue(searchMatrix.findElement(20));
  assertTrue(searchMatrix.findElement(23));
  assertTrue(searchMatrix.findElement(31));
  assertTrue(searchMatrix.findElement(45));
  assertTrue(searchMatrix.findElement(53));

  assertFalse(searchMatrix.findElement(55));
  assertFalse(searchMatrix.findElement(9));
  assertFalse(searchMatrix.findElement(14));
  assertFalse(searchMatrix.findElement(19));
  assertFalse(searchMatrix.findElement(39));

 }

 @Test(expected = NullPointerException.class)
 public void test2() {
  SearchMatrix searchMatrix = new SearchMatrix();
  searchMatrix.findElement(10);
 }

 @Test
 public void test3() {
  SearchMatrix searchMatrix = new SearchMatrix();
  int matrix[][] = { { 1, 2 } };

  searchMatrix.setMatrix(matrix);

  assertTrue(searchMatrix.findElement(1));
  assertTrue(searchMatrix.findElement(2));

  assertFalse(searchMatrix.findElement(55));
  assertFalse(searchMatrix.findElement(9));
  assertFalse(searchMatrix.findElement(14));
  assertFalse(searchMatrix.findElement(19));
  assertFalse(searchMatrix.findElement(39));

 }

 @Test
 public void test4() {
  SearchMatrix searchMatrix = new SearchMatrix();
  int matrix[][] = { { 1 }, { 2 } };

  searchMatrix.setMatrix(matrix);

  assertTrue(searchMatrix.findElement(1));
  assertTrue(searchMatrix.findElement(2));

  assertFalse(searchMatrix.findElement(55));
  assertFalse(searchMatrix.findElement(9));
  assertFalse(searchMatrix.findElement(14));
  assertFalse(searchMatrix.findElement(19));
  assertFalse(searchMatrix.findElement(39));

 }
}