PreviousNext
Coding/Searching and sorting

Count target in grid

Write codeMedium20 min

Your task

Given an m x n matrix in which each row is sorted in ascending order left-to-right and each column is sorted in ascending order top-to-bottom (but rows are NOT globally ordered relative to each other), count how many cells equal a given target. Aim for O(m + n) using the staircase walk; do not binary search every row. Dimensions up to 300 x 300.

Examples

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