Problem Statement

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

1. Each row is sorted in non-decreasing order.
2. 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.

Additional information

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

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

Brute Force

Intuition
The simplest approach is to ignore the sorted property and check every single element in the matrix. We iterate through every row and every column. If we find the target, return True. If we finish the scan without finding it, return False.

Algorithm

1. Iterate r from 0 to m-1.
2. Iterate c from 0 to n-1.
3. If matrix[r][c] == target, return True.
4. Return False.

def search_matrix(matrix: list[list[int]], target: int) -> bool:
    for row in matrix:
        for val in row:
            if val == target:
                return True
    return False

Time & Space Complexity

• Time complexity: O(m * n)

• Reason: We verify every element once.

• Space complexity: O(1)

• Reason: Constant extra space.

Binary Search (Optimal)

Intuition
Because the first integer of each row is greater than the last integer of the previous row, the entire matrix can be viewed as a single sorted 1D array of size m * n.

We can perform a standard binary search on this "virtual" 1D array.

• The range of indices is 0 to (m * n) - 1.
• To map a 1D index mid back to 2D coordinates (row, col), we use:
• row = mid // n (integer division by number of columns)
• col = mid % n (modulo by number of columns)

Algorithm

1. Get dimensions ROWS = len(matrix) and COLS = len(matrix[0]).
2. Initialize l = 0 and r = (ROWS * COLS) - 1.
3. While l <= r:

• Calculate mid = (l + r) // 2.
• Convert mid to 2D position: mid_val = matrix[mid // COLS][mid % COLS].
• If mid_val == target, return True.
• If mid_val < target, move left pointer l = mid + 1.
• If mid_val > target, move right pointer r = mid - 1.

4. Return False.

def search_matrix(matrix: list[list[int]], target: int) -> bool:
    if not matrix:
        return False
        
    ROWS, COLS = len(matrix), len(matrix[0])
    l, r = 0, (ROWS * COLS) - 1
    
    while l <= r:
        mid = (l + r) // 2
        mid_val = matrix[mid // COLS][mid % COLS]
        
        if mid_val == target:
            return True
        elif mid_val < target:
            l = mid + 1
        else:
            r = mid - 1
            
    return False

Time & Space Complexity

• Time complexity: O(log(m * n))

• Reason: Standard binary search on a range of size m * n.

• Space complexity: O(1)

• Reason: We only store pointers and dimensions.