Search in a 2D Matrix

Photo by Markus Spiske on Unsplash

Problem Description

You are given an m x n integer matrix matrix with the following two properties:

• Each row is sorted in non-decreasing order.
• The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in O(log(m * n)) time complexity.

Example 1:

Taken from Leetcode

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Example 2:

Taken from Leetcode

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

Constraints

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -10^4 <= matrix[i][j], target <= 10^4

Approach 1

The brute force approach traverses through the whole matrix, checking if each cell value is a target or not, if yes return true or false.

for (i = 0 to row) {
    for (j = 0 to col) {
        if (matrix[i][j] == target) {
          return true;
        }
    }
 }
return false;

Time Complexity and Space Complexity

Traversing the whole matrix costs us O(row * col) time.
There is no extra space being used, so space complexity is O(1)

Approach 2

We have each of the rows in a sorted order. This can give us a hint that if we traverse only the row and check if the 1st element of the current row and the last element of that current row are between our target, then do a binary search on that row.

• Traverse through the rows and check if matrix[currentrow][0] ≤ target and matrix[currentrow][column — 1] ≥ target, do a one-time binary search on matrix[currentrow]. We only do it one time as we are sure we will not be able to find the target beyond the current row, the target will be present since the array is sorted.

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) {
            return false;
        }
        int row = matrix.length;
        int col = matrix[0].length;
        for (int i = 0; i < row; i++) {
            if (matrix[i][0] <= target && matrix[i][col - 1] >= target) {
                return isFoundUsingBinarySearch(matrix[i], 0, col - 1, target);
            } 
        }
        return false;
    }

    private boolean isFoundUsingBinarySearch(int [] row, int low, int high, int target) {
        while (low <= high) {
            int middle = low + (high - low) / 2;
            if (row[middle] == target) {
                return true;
            }
            if (row[middle] > target) {
                high--;
            }
            else {
                low++;
            }
        }
        return false;
    }
}

Time Complexity and Space Complexity

• We are traversing each row and if we find a row where the target is in between do a one-time binary search.
  O(numberOfRows) + O(log(numberOfCol))
• Space Complexity : O(1)

Approach 3

Let us consider flattening the whole 2D matrix into a 1D matrix.

Taken from Leetcode

1D Matrix = [1,3,5,7,10,11,16,20,23,30,34,60]

This 1D matrix is sorted and we can do a binary search which will take logarithmic time. But still flattening the whole 2D matrix to a 1D matrix will take O(row * col) time complexity which is not optimal.

If we find the index of the corresponding row and column then we can still do a binary search inside the matrix without the overhead of flattening and storing it in an additional array.

Formula to convert the current index to equivalent row and col index

rowIndex = currentIndex / number of columns
colIndex = currentIndex % number of columns

This works because our matrix indexing starts from 0 index and says we have a 3 x 4 matrix and the 1D index might look like below if we have flattened the matrix.

0 1 2 3
4 5 6 7
8 9 10 11

1st row index is always the multiple of 4 as there are 4 elements in each row. Thus to get the row we divide by the number of columns.

Similarly, how many columns have gone by says about the column index, and thus we do a modulus operation.

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) {
            return false;
        }
        int row = matrix.length;
        int col = matrix[0].length;
        int low = 0;
        int high = row * col - 1;
        while (low <= high) {
            int middle = low + (high - low) / 2;
            int currentMiddleRowIndex = middle / col;
            int currentMiddleColIndex = middle % col;
            if (matrix[currentMiddleRowIndex][currentMiddleColIndex] == target) {
                return true;
            } 
            if (matrix[currentMiddleRowIndex][currentMiddleColIndex] > target) {
                high = middle - 1;
            }
            else {
                low = middle + 1;
            }
        }
        return false;
    }
}

Time Complexity and Space Complexity

• We are doing a binary search on the hypothetical flattened matrix of length O(row * col).
  Thus total time complexity = O(log(row * col)).
• Space Complexity O(1).