Algorithms for Coding Interviews in Java/

...

/

Solution: Search in Sorted Matrix

Solution: Search in Sorted Matrix

This review lesson gives a detailed analysis of the solutions to search for a key in a sorted matrix.

We'll cover the following...

Solution #1: Brute force

Press + to interact
class SearchMatrix {
 public static Object findKey(int[][] matrix, int numberOfRows, int numberOfColumns, int target) {
  for (int i = 0; i < numberOfRows; i++) {
   for (int j = 0; j < numberOfColumns; j++) {
    if (matrix[i][j] == target)
     return true;
   }
  }
  return false;
 }
 public static void main(String args[]) {
  int[][] matrix = {
      {10, 11, 12, 13},
      {14, 15, 16, 17},
      {27, 29, 30, 31},
      {32, 33, 39, 50}
    };
  // Example 1
  Object x = findKey(matrix, 4, 4, 80);
  System.out.println("Search for 80 returned: " + x);
  
  // Example 2
  x = findKey(matrix, 4, 4, 15);
  System.out.println("Search for 15 returned: " + x);
 }
}

This is a simple linear search of a 2-D matrix. We use two for loops to iterate over the entire matrix and see if a value equal to the given target is found (lines 3-6).

Time complexity

Since we use two nested for loops, the time complexity is O(n∗m)O(n*m) ...