Search a 2D Matrix

Problem Summary

• Given a 2D matrix, where each row is in sorted order and furthermore, first element of each row is bigger than last element of prev row

What is Being Asked?

• Do a Binary Search on both row and column

Main Concepts Used

• Binary Search

Time & Space Complexity

• Time: $O(log(m\ast n))$ → Reason: $O(logm)$ to find the column and $O(logn)$ to find the row
• Space: $O(1)$ → Reason: No extra storage required except a few pointers

Code

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        up, down = 0, len(matrix) - 1
        while up <= down:
            m = (up + down) // 2
            current_row = matrix[m]

            if target < current_row[0]:
                down = m - 1
            elif target > current_row[-1]:
                up = m + 1
            else:  # number can or cannot be in the current row, do a binary search
                l, r = 0, len(current_row) - 1
                while l <= r:
                    mid = (l + r) // 2
                    if current_row[mid] == target:
                        return True
                    elif current_row[mid] > target:
                        r = mid - 1
                    else:
                        l = mid + 1
                return False
        return False

Common Mistakes / Things I Got Stuck On

• Forgot to return False after both while loops
  Note: Look at even further cleaner code in the solution. Using divmod and treating matrix as a single flattened array.