Search a 2D Matrix II in Python

You get a grid of integers, matrix, with m rows and n columns. You also get an integer target.

Return True if matrix contains target, and False if it doesn't.

The grid is sorted in two ways:

• Each row goes from smallest to largest, left to right.
• Each column goes from smallest to largest, top to bottom.

Equal neighbors are allowed. A row's first value can be smaller than the last value of the row above.

The tests search the same grid for many targets, one call per target.

The grid is a list of rows. Each row is a list of integers. Rows are counted from 0 at the top, columns from 0 at the left.

Example 1:

Input: matrix = [
  [3, 8, 12, 20],
  [5, 9, 15, 24],
  [7, 14, 18, 30]
], target = 15
Output: True
Explanation: 15 is in row 1, column 2.

Example 2:

Input: matrix = [
  [3, 8, 12, 20],
  [5, 9, 15, 24],
  [7, 14, 18, 30]
], target = 13
Output: False
Explanation: The grid has 12 and 14, but no 13.

Example 3:

Input: matrix = [
  [-6, -2, 0],
  [-4, 1, 1]
], target = -4
Output: True
Explanation: -4 is in row 1, column 0.
Row 1 starts with -4, but row 0 ends with 0.
The two rows overlap, and that's allowed.

Constraints:

• 1 to 300 rows.
• 1 to 300 columns.
• All rows have the same length.
• Every value and target are from -10⁹ to 10⁹.
• Up to 5,000 targets for one grid.
• The grid follows the two rules above.