Search a Sorted Grid

A grid of numbers is sorted two ways: every row is non-decreasing from left to right, and every column is non-decreasing from top to bottom. Decide whether a target value appears anywhere in it.

Reading every cell works, but it costs \(R \times C\) steps for an \(R \times C\) grid. The two orders together let you do it in \(O(R + C)\): each comparison should rule out a whole row or a whole column.

Implement search_sorted_grid(grid, target) returning True when target is in the grid and False otherwise. The grid may be empty, or have rows of length zero; neither contains anything.

Examples

grid = [
    [1, 4, 7, 11],
    [2, 5, 8, 12],
    [3, 6, 9, 16],
    [10, 13, 14, 17],
]

search_sorted_grid(grid, 5)
# True

search_sorted_grid(grid, 15)
# False  (no row or column contains 15)

Constraints

• The grid has \(R\) rows of \(C\) values each, \(0 \le R, C \le 2000\). It need not be square.
• Every value and the target fit in a signed 64-bit integer. Values may repeat.
• The largest hidden test asks thousands of targets against one large grid. Scanning the grid for each target will not finish in time.

In C++

bool search_sorted_grid(const std::vector<std::vector<long long>>& grid,
                        long long target);