Search for a Value in a Matrix Sorted as One Continuous Sequence
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
You are given an `m x n` integer matrix with two ordering properties: every row is sorted in non-decreasing order, and the first value of each row is strictly greater than the last value of the row above it. Decide whether a given `target` appears anywhere in the matrix.
### Function Signature
```python
def matrix_contains(matrix: List[List[int]], target: int) -> bool:
```
### Rules
- Return `True` if at least one cell equals `target`, otherwise `False`.
- The input always satisfies both ordering properties; you do not need to validate it.
- Aim for running time logarithmic in `m * n`.
### Constraints
- `m == len(matrix)`, `n == len(matrix[i])` for every row, all rows have the same length
- `1 <= m <= 100` and `1 <= n <= 100`
- `-10^4 <= matrix[i][j] <= 10^4`
- `-10^4 <= target <= 10^4`
### Examples
**Example 1**
```text
Input: matrix = [[2, 4, 9], [11, 15, 18], [21, 30, 41]], target = 15
Output: True
```
**Example 2**
```text
Input: matrix = [[2, 4, 9], [11, 15, 18], [21, 30, 41]], target = 10
Output: False
```
10 would fall between the end of the first row (9) and the start of the second row (11), so it is not present.
**Example 3**
```text
Input: matrix = [[-3, -3, 0]], target = -3
Output: True
```
Rows may contain repeated values.
Overview: Decide whether a target value appears in a matrix whose rows are sorted and whose every row starts above the previous row's last value. It tests exploiting that ordering to search in logarithmic time and handling single-row, repeated-value and boundary cases correctly.
Read the full Amazon Software Engineer interview experience this question came from
