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

Example function shape:

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

Examples

Example 1:

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

Output:

True

The diagonals are:

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

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

Example 2:

matrix = [
    [1, 2],
    [2, 2],
]

Output:

False

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

[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:

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:

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:

m = number of rows
n = number of columns

Implementation

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:

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.

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:

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

If any comparison fails, the matrix cannot be Toeplitz.

If all comparisons pass:

return True

the matrix is Toeplitz.

Testing

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: