PreviousNext
Coding/Searching and sorting

Search sorted matrix

Write codeMedium20 minAmazon style

Your task

Given an m x n integer matrix where each row is sorted ascending left-to-right and each column is sorted ascending top-to-bottom, determine whether a target value exists in the matrix. Return True or False. Aim for O(m + n) time. The matrix has at least one row and one column.

Examples

search_matrix_staircase(matrix: list[list[int]], target: int) -> bool
Example 1
Inputsearch_matrix_staircase([[1, 4, 7, 11], [2, 5, 8, 12], [3, 6, 9, 16], [10, 13, 14, 17]], 5)
OutputTrue