Problem 74. Search a 2D Matrix [Medium]

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.

My Solution [Time: O(log(m*n)), Space: O(1)]

def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        c = len(matrix[0])
        r = len(matrix)
        i = 0
        j = r*c - 1
        while i <= j:
            m = i + (j-i)//2
            if matrix[m//c][m%c] < target:
                i = m + 1
            elif matrix[m//c][m%c] > target:
                j = m - 1
            else:
                return True
        return False

Got to use binary search (covered in a post yesterday) on an unfamiliar problem. The only tricky part is how to handle the middle value with the column/rows. We use modulo and floor division to get the column and row indicies. We can treat the 2D matrix effectively as a flattened 1D array because how the matrix is sorted. This is the optimal solution to the problem.