Search a sorted matrix

Hard

Given a sorted 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.

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

matrix = [
    [1, 3, 8],
    [9, 21, 24],
    [25, 28, 32]
]
target = 7

Your function should return False.

Given the same matrix, if the target is 21, your function should return True.

Note that every row is sorted. Each row starts with a number that is greater than the last number from the previous row.

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

Solution

Time and Space Complexity

Since we cut the problem in half in each iteration, the time complexity is O(log n).

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

5 Essential Sorting & Searching Coding Interview Problems

Master Sorting & Searching by trying the coding challenges below.

Previous Lesson

Intersection of Arrays

Next Lesson

Search row & col sorted matrix

Want to confidently pass your next coding interview?

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