Matrix Search Editorial

Practice Problem Link: Matrix Search | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a matrix, check if the matrix contains a given key.

The matrix has the following properties:

• Integer in each row is arranged in non-decreasing order from left to right.
• The first integer in every row is greater than the last integer in the previous row.

Naive Approach

Let's say there are n rows and m columns. The simple way is to compare the key value with every matrix element. Run two nested loops and if at any point the key value is equal to the matrix element, return true. Otherwise, return false at the end.

Analysis

• Time Complexity: O(n*m)
• Space Complexity: O(1)

Implementation

C++

bool searchMatrix(vector<vector<int>> &matrix, int key) {
   int rowSize = matrix.size(), columnSize = matrix[0].size();
   for (int i = 0; i < rowSize; i++) {
       for (int j = 0; j < columnSize; j++) {
           if (matrix [i][j] == key) {
               return true;
           }
       }
   }
   return false;
}

Java

class Solution {
   boolean searchMatrix(int[][] matrix, int key) {
       int rowSize = matrix.length, columnSize = matrix[0].length;
       for (int i = 0; i < rowSize; i++) {
           for ( int j = 0; j < columnSize; j++) {
               if (matrix [i][j] == key) {
                   return true;
               }
           }
       }
       return false;
   }
}

Optimal Approach

The problem can be solved by using two binary searches since the matrix is sorted in row-major order. 

• First, perform a binary search for the whole matrix and check that for any row, the first element of the row is less than or equal to the key and the last element of the row is greater than or equal to the key.
• After finding such a row, perform a binary search on that row to find the key-value and return true.
• If the key value is not found, return false.

Analysis

• Time Complexity: O(log(n*m))
• Space Complexity: O(1)

Implementation

C++ (Iterative)

bool searchMatrix(vector<vector<int>> &matrix, int key) {
   int rowSize = matrix.size(), columnSize = matrix[0].size();
   int low = 0, high = rowSize - 1, mid, row = - 1;
   while (low <= high) {
       mid = (high + low) / 2;
       if (matrix [mid][0] <= key && matrix [mid][columnSize - 1] >= key) {
           row = mid;
           break;
       } else if (matrix [mid][0] > key ) {
           high = mid - 1;
       } else {
           low = mid + 1;
       }
   }
   
   if (row == - 1) {
       return false;
   } else {
       low = 0;
       high = columnSize-1;
       while (low <= high) {
           mid = (high + low) / 2;
           if (matrix [row][mid] == key) {
               return true;
           } else if (matrix [row][mid] < key) {
               low = mid + 1;
           } else {
               high = mid - 1;
           }
       }
       return false;
   }
}

C++ (Recursive)

bool findKey(vector<int> &arr, int low, int high, int key) {
   if (high >= low) {
       int mid = (high + low) / 2;
       if (arr[mid] == key) {
           return true;
       } else if (arr[mid] < key) {
           return findKey (arr, mid + 1, high, key);
       } else {
           return findKey (arr, low, mid - 1, key);
       }
   }
   return false;
}
bool searchMatrix(vector<vector<int>> &matrix, int key) {
   int rowSize = matrix.size(), columnSize = matrix[0].size();
   int low = 0, high = rowSize - 1, mid;
   while (low <= high) {
       mid = (high + low) / 2;
       if (matrix [mid][0] <= key && matrix [mid][columnSize - 1] >= key) {
           return findKey (matrix [mid], 0, columnSize - 1, key);
       } else if (matrix [mid][0] > key ) {
           high = mid - 1;
       } else {
           low = mid + 1;
       }
   }
   return false;
}

Java (Iterative)

class Solution {
   boolean searchMatrix(int[][] matrix, int key){
       int rowSize = matrix.length, columnSize = matrix[0].length;
       int low = 0, high = rowSize - 1, mid, row = - 1;
       while (low <= high) {
           mid = (high + low) / 2;
           if (matrix [mid][0] <= key && matrix [mid][columnSize - 1] >= key) {
               row = mid;
               break;
           } else if (matrix [mid][0] > key ) {
               high = mid - 1;
           } else {
               low = mid + 1;
           }
       }
   
       if (row == - 1) {
           return false;
       } else {
           low = 0;
           high = columnSize - 1;
           while (low <= high) {
               mid = (high + low) / 2;
               if (matrix [row][mid] == key) {
                   return true;
               } else if (matrix [row][mid] < key) {
                   low = mid + 1;
               } else {
                   high = mid - 1;
               }
           }
           return false;
       }
   }
}

Java (Recursive)

class Solution {
   boolean findKey(int[] arr, int low, int high, int key) {
       if (high >= low) {
           int mid = (high + low) / 2;
           if (arr[mid] == key) {
               return true;
           } else if(arr[mid] < key) {
               return findKey (arr, mid + 1, high, key);
           } else {
               return findKey (arr, low, mid - 1, key);
           }
       }
       return false;
   }
   boolean searchMatrix(int[][] matrix, int key){
       int rowSize = matrix.length, columnSize = matrix[0].length;
       int low = 0, high = rowSize - 1, mid;
       while (low <= high) {
           mid = (high + low) / 2;
           if (matrix [mid][0] <= key && matrix [mid][columnSize-1] >= key) {
               return findKey (matrix [mid], 0, columnSize - 1, key);
           } else if (matrix [mid][0] > key ) {
               high = mid - 1;
           } else {
               low = mid + 1;
           }
       }
       return false;
   }
}