# LeetCode 766: Toeplitz Matrix

## Problem Restatement

We are given an `m x n` matrix.

Return `True` if the matrix is Toeplitz. Otherwise, return `False`.

A matrix is Toeplitz if every diagonal from top-left to bottom-right contains the same value. In other words, each cell should match the cell directly above-left from it.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer matrix `matrix` |
| Output | `True` if the matrix is Toeplitz, otherwise `False` |
| Diagonal direction | Top-left to bottom-right |
| Main rule | `matrix[r][c] == matrix[r - 1][c - 1]` for all valid `r, c` |

Example function shape:

```python
def isToeplitzMatrix(matrix: list[list[int]]) -> bool:
    ...
```

## Examples

Example 1:

```python
matrix = [
    [1, 2, 3, 4],
    [5, 1, 2, 3],
    [9, 5, 1, 2],
]
```

Output:

```python
True
```

The diagonals are:

```text
[9]
[5, 5]
[1, 1, 1]
[2, 2, 2]
[3, 3]
[4]
```

Every diagonal has equal values, so the matrix is Toeplitz.

Example 2:

```python
matrix = [
    [1, 2],
    [2, 2],
]
```

Output:

```python
False
```

The diagonal from top-left to bottom-right is:

```text
[1, 2]
```

The values are different, so the matrix is not Toeplitz.

## First Thought: Check Each Diagonal

One direct way is to start every diagonal from the first row and first column.

Then follow each diagonal down-right and check whether every value is the same.

This works, but there is an even simpler way.

Every cell belongs to exactly one top-left to bottom-right diagonal. For a diagonal to be valid, every cell except the first cell on that diagonal must equal its previous diagonal neighbor.

So instead of explicitly listing diagonals, we can compare each cell with its upper-left neighbor.

## Key Insight

A matrix is Toeplitz exactly when this condition holds for every cell not in the first row or first column:

```python
matrix[r][c] == matrix[r - 1][c - 1]
```

Why?

If every cell equals the previous cell on its diagonal, then by repeated equality, all cells on that diagonal are equal.

So we only need one pass through the matrix.

## Algorithm

1. Let `rows = len(matrix)`.
2. Let `cols = len(matrix[0])`.
3. For every row `r` from `1` to `rows - 1`:
   1. For every column `c` from `1` to `cols - 1`:
      1. Compare `matrix[r][c]` with `matrix[r - 1][c - 1]`.
      2. If they are different, return `False`.
4. If no mismatch is found, return `True`.

## Correctness

The algorithm checks every cell that has an upper-left neighbor.

If it finds a cell `matrix[r][c]` where:

```python
matrix[r][c] != matrix[r - 1][c - 1]
```

then the diagonal containing those two cells has different values. Therefore, the matrix is not Toeplitz, and returning `False` is correct.

If the algorithm finishes without finding any mismatch, then every cell equals its upper-left neighbor. Along any top-left to bottom-right diagonal, each value equals the value before it. By transitivity, all values on that diagonal are equal.

Therefore, every diagonal satisfies the Toeplitz condition, so returning `True` is correct.

## Complexity

Let:

```text
m = number of rows
n = number of columns
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(m * n)` | Each non-first-row and non-first-column cell is checked once |
| Space | `O(1)` | Only loop variables are used |

## Implementation

```python
class Solution:
    def isToeplitzMatrix(self, matrix: list[list[int]]) -> bool:
        rows = len(matrix)
        cols = len(matrix[0])

        for r in range(1, rows):
            for c in range(1, cols):
                if matrix[r][c] != matrix[r - 1][c - 1]:
                    return False

        return True
```

## Code Explanation

We first get the matrix dimensions:

```python
rows = len(matrix)
cols = len(matrix[0])
```

Then we start from row `1` and column `1` because cells in row `0` or column `0` do not have an upper-left neighbor.

```python
for r in range(1, rows):
    for c in range(1, cols):
```

For each cell, we compare it with the previous cell on the same diagonal:

```python
if matrix[r][c] != matrix[r - 1][c - 1]:
    return False
```

If any comparison fails, the matrix cannot be Toeplitz.

If all comparisons pass:

```python
return True
```

the matrix is Toeplitz.

## Testing

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

    assert s.isToeplitzMatrix([
        [1, 2, 3, 4],
        [5, 1, 2, 3],
        [9, 5, 1, 2],
    ]) is True

    assert s.isToeplitzMatrix([
        [1, 2],
        [2, 2],
    ]) is False

    assert s.isToeplitzMatrix([
        [7],
    ]) is True

    assert s.isToeplitzMatrix([
        [1, 2, 3],
    ]) is True

    assert s.isToeplitzMatrix([
        [1],
        [2],
        [3],
    ]) is True

    assert s.isToeplitzMatrix([
        [1, 2, 3],
        [4, 1, 2],
        [5, 4, 1],
    ]) is True

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Standard Toeplitz matrix | Confirms all diagonals match |
| Mismatch on main diagonal | Confirms false case |
| Single cell | Always Toeplitz |
| Single row | Every diagonal has one value |
| Single column | Every diagonal has one value |
| Square Toeplitz matrix | Confirms repeated diagonal comparison |