# LeetCode 240: Search a 2D Matrix II

## Problem Restatement

We are given an `m x n` integer matrix and an integer `target`.

The matrix has two sorted properties:

- Each row is sorted in ascending order from left to right.
- Each column is sorted in ascending order from top to bottom.

We need to return `True` if `target` exists in the matrix, and `False` otherwise.

LeetCode examples include searching for `5`, which returns `true`, and searching for `20`, which returns `false`, in the same sorted matrix. The constraints allow `1 <= m, n <= 300`, and values can be between `-10^9` and `10^9`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Matrix `matrix`, integer `target` |
| Output | `True` if target exists, otherwise `False` |
| Row property | Each row is sorted left to right |
| Column property | Each column is sorted top to bottom |

Function shape:

```python
class Solution:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        ...
```

## Examples

Example 1:

```text
Input:
matrix = [
  [1, 4, 7, 11, 15],
  [2, 5, 8, 12, 19],
  [3, 6, 9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
target = 5

Output: true
```

The value `5` exists at row `1`, column `1`.

Example 2:

```text
Input:
matrix = [
  [1, 4, 7, 11, 15],
  [2, 5, 8, 12, 19],
  [3, 6, 9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
target = 20

Output: false
```

The value `20` does not exist in the matrix.

## First Thought: Search Every Cell

The simplest method is to check every cell.

```python
class Solution:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        for row in matrix:
            for value in row:
                if value == target:
                    return True

        return False
```

This is correct, but it ignores the sorted structure.

If the matrix has `m` rows and `n` columns, this takes:

```text
O(m * n)
```

We can do better.

## Key Insight

Start from the top-right corner.

At position `(row, col)`, let:

```text
value = matrix[row][col]
```

This position is special because:

- Everything to the left is smaller or equal.
- Everything below is larger or equal.

So we can eliminate one row or one column each step.

### If value is too large

If:

```text
value > target
```

then every value below it in the same column is also too large, because columns are sorted top to bottom.

So the target cannot be in this column.

Move left:

```python
col -= 1
```

### If value is too small

If:

```text
value < target
```

then every value to the left in the same row is also too small, because rows are sorted left to right.

So the target cannot be in this row.

Move down:

```python
row += 1
```

### If value equals target

Return `True`.

## Algorithm

1. Start at the top-right corner:
   - `row = 0`
   - `col = n - 1`
2. While `row < m` and `col >= 0`:
   - If `matrix[row][col] == target`, return `True`.
   - If `matrix[row][col] > target`, move left.
   - If `matrix[row][col] < target`, move down.
3. If we leave the matrix, return `False`.

## Walkthrough

Use the matrix:

```text
[
  [1, 4, 7, 11, 15],
  [2, 5, 8, 12, 19],
  [3, 6, 9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
```

Search for:

```text
target = 5
```

Start at top-right:

| Position | Value | Comparison | Move |
|---|---:|---|---|
| `(0, 4)` | `15` | `15 > 5` | left |
| `(0, 3)` | `11` | `11 > 5` | left |
| `(0, 2)` | `7` | `7 > 5` | left |
| `(0, 1)` | `4` | `4 < 5` | down |
| `(1, 1)` | `5` | found | return `True` |

## Correctness

At every step, the algorithm is positioned at some cell `(row, col)`.

If `matrix[row][col] > target`, then every value below it in column `col` is also greater than or equal to `matrix[row][col]`, and therefore greater than `target`. So column `col` cannot contain the target in any remaining row. Moving left removes only impossible cells.

If `matrix[row][col] < target`, then every value to the left in row `row` is less than or equal to `matrix[row][col]`, and therefore less than `target`. So row `row` cannot contain the target in any remaining column. Moving down removes only impossible cells.

If `matrix[row][col] == target`, the algorithm returns `True`, which is correct.

Each move eliminates one full row or one full column from the remaining search area. Since the algorithm only removes cells that cannot contain the target, it never discards a valid answer.

If the search exits the matrix, all possible rows or columns have been eliminated, so the target does not exist in the matrix. Returning `False` is correct.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(m + n)` | Each step moves one row down or one column left |
| Space | `O(1)` | Only two indices are stored |

Here, `m` is the number of rows, and `n` is the number of columns.

## Implementation

```python
class Solution:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        m = len(matrix)
        n = len(matrix[0])

        row = 0
        col = n - 1

        while row < m and col >= 0:
            value = matrix[row][col]

            if value == target:
                return True

            if value > target:
                col -= 1
            else:
                row += 1

        return False
```

## Code Explanation

Get the matrix size:

```python
m = len(matrix)
n = len(matrix[0])
```

Start from the top-right corner:

```python
row = 0
col = n - 1
```

Continue while the position is valid:

```python
while row < m and col >= 0:
```

Check the current value:

```python
value = matrix[row][col]
```

If it matches, return immediately:

```python
if value == target:
    return True
```

If the value is too large, move left:

```python
if value > target:
    col -= 1
```

Otherwise, the value is too small, so move down:

```python
else:
    row += 1
```

If the loop ends, the target was not found:

```python
return False
```

## Alternative: Binary Search Each Row

Because each row is sorted, we can binary search every row.

This gives:

```text
O(m log n)
```

That is valid, but the top-right method is usually better because it uses both row and column sorting.

## Testing

```python
def run_tests():
    s = Solution()

    matrix = [
        [1, 4, 7, 11, 15],
        [2, 5, 8, 12, 19],
        [3, 6, 9, 16, 22],
        [10, 13, 14, 17, 24],
        [18, 21, 23, 26, 30],
    ]

    assert s.searchMatrix(matrix, 5) is True
    assert s.searchMatrix(matrix, 20) is False
    assert s.searchMatrix([[1]], 1) is True
    assert s.searchMatrix([[1]], 2) is False
    assert s.searchMatrix([[1, 3, 5]], 3) is True
    assert s.searchMatrix([[1], [3], [5]], 4) is False
    assert s.searchMatrix([[-5, -3, 0], [-2, 1, 4], [2, 6, 9]], -3) is True

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| Standard matrix, target `5` | Target exists |
| Standard matrix, target `20` | Target missing |
| `[[1]]`, target `1` | Single-cell hit |
| `[[1]]`, target `2` | Single-cell miss |
| Single row | Horizontal movement |
| Single column | Vertical movement |
| Negative values | General integer handling |