Search a row and column sorted matrix

Hard

Given a matrix of numbers of size m x n, and a target number, write a function that determines if the target number exists in the matrix.

Every row and every column is sorted in ascending order in the given matrix.

For example, if your function recieves the following 3x3 matrix and target number:

matrix = [
    [1, 3, 8, 10],
    [2, 5, 9, 11],
    [3, 6, 10, 15],
    [5, 7, 12, 18],
]
target = 6

Your function should return True.

Given the same matrix, if the target is 4, your function should return False.

Note how in matrix, every row and column is sorted, but is not necessarily greater than the previous row or column.

Try it

Before you look at the solution, try to code it yourself.

def search_matrix(matrix: list[list[int]], target: int) -> bool:
    # implement search_matrix
    return False

1def search_matrix(matrix: list[list[int]], target: int) -> bool:
2    # implement search_matrix
3    return False
4

On each iteration we either remove an entire row or an entire column.

Therefore, our time complexity is O(m + n).

There is no additional space required. So the space complexity constant O(1).

Master Sorting & Searching by trying the coding challenges below.

Stack Bash helps new and veteran software engineers master data structures and algorithms for technical interviews.