74. Search a 2D Matrix.md

74. Search a 2D Matrix

1. Description

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

Example 1:

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

Example 2:

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

2. Solutions

Solution 1: Language: Python $O(\log(mn))$ Binary Search by treating is as 1D Array

We could treat the 2D matrix as 1D one by creating a new list. However, we could use value = matrix[mid // col][mid % col] inplace directly that no need to waste extra space creating a 1D array. Then, we use the binary search to find if there is the target we want.

• Thursday 21 October, 2021
• Time Complexity: $O(\log(m \times n))$
• Space Complexity: $O(m \times n)$
• Runtime: 28 ms, faster than 80.91% of Python online submissions for Search a 2D Matrix.
• Memory Usage: 13.8 MB, less than 75.83% of Python online submissions for Search a 2D Matrix.

class Solution_One(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        seq = []
        row = len(matrix)

        for i in range(row):
            seq += matrix[i]

        l = 0
        r = len(seq) - 1

        while l <= r:
            mid = (l + r) // 2
            if seq[mid] == target:
                return True
            elif seq[mid] < target:
                l = mid + 1
            else:
                r = mid - 1

        return False

Solution 2: Language: Python $O(\log(mn))$ Twice Binary Search

In this solution, I used the binary search twice. First one is using to searching the column, and the second one searching the row we found in the first searching operation.

The time complexity is $$O(\log m) + O(\log n) = O(\log m + \log n) = O(\log{m \times n})$$ which is equal to our first solution.

• Thursday 21 October, 2021
• Time Complexity: $O(\log(m \times n))$
• Space Complexity: $O(m \times n)$
• Runtime: 28 ms, faster than 80.91% of Python online submissions for Search a 2D Matrix.
• Memory Usage: 13.8 MB, less than 75.83% of Python online submissions for Search a 2D Matrix.

class Solution_Two(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        firstColumn = self.column(matrix, 0)
        index = self.searchColumn(firstColumn, target)
        if index == -1:
            return True
        elif index == -2:
            return False
        else:
            return self.searchRow(matrix[index], target)

    def searchRow(self, row, target):
        l = 0
        r = len(row) - 1
        while l <= r:
            mid = (l + r) // 2
            if row[mid] == target:
                return True
            elif row[mid] < target:
                l = mid + 1
            else:
                r = mid - 1
        return False

    def searchColumn(self, column, target):
        l = 0
        r = len(column) - 1
        while l <= r:
            mid = (l + r) // 2
            if column[mid] == target:
                return -1
            if column[mid] < target:
                ## The order for the following if..or statement could not be exchanged.
                ## Otherwise, it might caused an IndexError: list index out of range.
                if mid == len(column) - 1 or column[mid + 1] > target:
                    return mid
                else:
                    l = mid + 1
            else:
                r = mid - 1
        return -2

    def column(self, matrix, i):
        return [row[i] for row in matrix]