Search A 2D Matrix

Question

You are given an m x n 2-D integer array matrix and an integer target.

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

Return true if target exists within matrix or false otherwise.

Can you write a solution that runs in O(log(m * n)) time?

Example 1:

Input: matrix = [[1,2,4,8],[10,11,12,13],[14,20,30,40]], target = 10

Output: true

Example 2:

Input: matrix = [[1,2,4,8],[10,11,12,13],[14,20,30,40]], target = 15

Output: false

Constraints:

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

Solution

Intuition

If we want to do binary search, we need to find a way to convert from a regular index to the position in the array. Since the matrix is filled by the column, we have a formular

def _arrayPosition(self, index: int, nRow: int, nCol: int) -> Tuple[int, int]:
    return (index // nCol, index % nCol)

Implementation

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        nRow, nCol = len(matrix), len(matrix[0])
        left, right = 0, nRow * nCol - 1

        while left <= right:
            middle = (left + right) // 2
            row, col = self._arrayPosition(middle, nRow, nCol)
            
            value = matrix[row][col]
            
            if value == target:
                return True
            elif value < target:
                left = middle + 1
            else:
                right = middle - 1
        
        return False
    
    def _arrayPosition(self, index: int, nRow: int, nCol: int) -> Tuple[int, int]:
        return (index // nCol, index % nCol)

Time Complexity

• Time: $O(log (m \times n))$
• Space: $O(1)$