Matrix Search Sequel

Given a two-dimensional integer matrix, where every row and column is sorted in ascending order, return whether an integer target exists in the matrix.

This should be done in \(\mathcal{O}(n + m)\) time.

Constraints

• n, m ≤ 250 where n and m are the number of rows and columns in matrix

https://binarysearch.com/problems/Matrix-Search-Sequel

Examples

Example 1

Input

• matrix =

[[ 1, 3, 9],
 [ 2, 5,10],
 [ 5, 7,13]]

• target = 7

Output

• answer = True

Solution