Here is solutions for Search a 2D Matrix.

1. Understand the Problem

Given a 2D matrix where:

• Each row is sorted in ascending order

• The first element of each row is greater than the last element of the previous row

Determine if a target exists in the matrix.

2. Clarify 3 - 4 Constraints

1. Are matrix rows guaranteed to be sorted in ascending order?

2. Are row ranges non-overlapping? (i.e., last element of row i < first element of row i+1?)

3. What are the time and space constraints? (Usually O(log (m × n)) expected).

4. Can the matrix be empty or contain only one row/column?

5. What should we return if target is not found? (→ return False)

3. Explore examples

4. Brainstorm 2 - 3 solutions

4.1. Solution 1: Naive Linear Scan (Brute Force) - O(M * N)

• Check every element one by one.

• Time: O(m × n)

• Space: O(1)

4.2. Solution 2: Top-right (Go from top-right) Search - O(M + N)

Start at top-right:

• If current > target → move left

• If current < target → move down

• Time: O(m + n) => You skip all the row, do not traverse all, worst case: Go to the last row, traverse all the last row.

• Space: O(1)

4.3. Solution 3: Row Search First + Binary Search - O(log m + log n)

• First, identify the possible row (since each row is like independent range).

• Then, perform binary search in that row.

• Time: O(log m + log n)

• Space: O(1)

4.4. Solution 4: Treat matrix as 1D array - O(log(m * n))

• Index mapping: value_at(index) = matrix[index // n][index % n]

• Perform regular binary search over total length m × n

• Time: O(log(m × n))

• Space: O(1)

5. Implement solutions

5.1. Brute Force - O(M * N)

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        for r in range(len(matrix)):
            for c in range(len(matrix[0])):
                if matrix[r][c] == target:
                    return True
        return False

• Time: O(M * N).

• Space: O(1).

5.2. Top-right corner Search - O(M + N)

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        r, c = 0, n - 1

        while r < m and c >= 0:
            if matrix[r][c] > target:
                c -= 1
            elif matrix[r][c] < target:
                r += 1
            else:
                return True
        return False

• Time: O(M + N).

• Space: O(1).

5.3. Binary Search 2D Array - O(logM + logN)

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        ROWS, COLS = len(matrix), len(matrix[0])

        top, bot = 0, ROWS - 1
        while top <= bot:
            row = (top + bot) // 2
            if target > matrix[row][-1]:
                top = row + 1
            elif target < matrix[row][0]:
                bot = row - 1
            else:
                break

        if not (top <= bot):
            return False
        row = (top + bot) // 2
        l, r = 0, COLS - 1
        while l <= r:
            m = (l + r) // 2
            if target > matrix[row][m]:
                l = m + 1
            elif target < matrix[row][m]:
                r = m - 1
            else:
                return True
        return False

• Time: O(logM + logN).

• Space: O(1).

5.4. Binary Search 1D Aray - O(log(M * N))

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        ROWS, COLS = len(matrix), len(matrix[0])

        l, r = 0, ROWS * COLS - 1
        while l <= r:
            m = l + (r - l) // 2
            row, col = m // COLS, m % COLS
            if target > matrix[row][col]:
                l = m + 1
            elif target < matrix[row][col]:
                r = m - 1
            else:
                return True
        return False

• Time: O(log(M * N)).

• Space: O(1).

6. Dry run examples

matrix = [
    [1,  3,  5,  7],
    [10, 11, 16, 20],
    [23, 30, 34, 60]
]
target = 16
m = 3 rows, n = 4 columns

6.1. Row Selection + Binary Search → O(log M + log N)

6.2. Treat Matrix as 1D → O(log(M × N))