LeetCode 766 - Toeplitz Matrix

Difficulty: 🟢 Easy
Topics: Array, Matrix

Solution

Problem Understanding

The problem asks us to determine whether a given matrix satisfies the Toeplitz property. A matrix is considered Toeplitz if every diagonal running from the top-left corner toward the bottom-right corner contains identical values.

More formally, for every valid position (row, col) in the matrix, the value at that position must match the value diagonally down and to the right, meaning:

$matrix[row][col] = matrix[row+1][col+1]$

whenever (row + 1, col + 1) is still inside the matrix bounds.

The input is a two-dimensional integer array with m rows and n columns. The task is to return true if all diagonals satisfy the Toeplitz condition, otherwise return false.

The constraints are relatively small:

1 <= m, n <= 20
Matrix values are between 0 and 99

Because the matrix dimensions are tiny, even less efficient approaches would pass comfortably. However, the goal is to design a clean and optimal solution that scales well conceptually and also addresses the follow-up questions involving limited memory access.

Several edge cases are important to recognize immediately:

A single row matrix is always Toeplitz because there are no diagonals with multiple elements.
A single column matrix is also always Toeplitz.
Very small matrices such as 1 x 1 should return true.
Matrices where only one diagonal violates the rule should correctly return false.
Rectangular matrices must work correctly, not just square matrices.

The problem guarantees that the matrix is non-empty and properly rectangular, so we do not need to handle malformed input.

Approaches

Brute Force Approach

A straightforward brute-force approach is to explicitly examine every diagonal independently.

We can start a diagonal from every cell in the first row and every cell in the first column. For each starting point, we move diagonally downward while checking whether all elements match the first element in that diagonal.

This approach is correct because every top-left to bottom-right diagonal is visited exactly once, and every element in each diagonal is compared against the expected value.

However, this method performs redundant work. Many cells are revisited multiple times while traversing overlapping diagonals. Although the constraints are small enough that this still works efficiently in practice, it is not the cleanest or most optimal way to solve the problem.

Optimal Approach

The key observation is that each cell only needs to match the element immediately up-left from it.

If the matrix is Toeplitz, then:

$matrix[row][col] = matrix[row-1][col-1]$

for every cell except those in the first row or first column.

This insight dramatically simplifies the problem. Instead of traversing entire diagonals, we only compare each element with its top-left neighbor once.

If every such comparison succeeds, then every diagonal must contain identical values.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m × n × min(m, n))	O(1)	Traverses each diagonal independently
Optimal	O(m × n)	O(1)	Compares each cell with its top-left neighbor once

Algorithm Walkthrough

Start iterating from the second row because the first row has no top-left neighbor.
For each row, start iterating from the second column because the first column also has no top-left neighbor.
At each position (row, col), compare the current value with the value at (row - 1, col - 1).
If the two values differ, immediately return False because the Toeplitz property has been violated.
Continue scanning the entire matrix if all comparisons succeed.
If the loop completes without finding any mismatch, return True.

Why it works

The core invariant is that every element must equal the element diagonally above and to the left. If this condition holds for every valid cell, then every diagonal consists entirely of repeated values.

Because every diagonal is formed by repeatedly moving down-right, ensuring equality between neighboring diagonal elements guarantees that the entire diagonal remains constant.

Python Solution

from typing import List

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

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

        return True

The implementation begins by storing the number of rows and columns for readability and efficiency.

The outer loop starts at row index 1 because elements in the first row do not have a top-left neighbor. Similarly, the inner loop starts at column index 1.

For every cell, the code compares the current value with the value diagonally above and to the left. If a mismatch is found, the function immediately returns False.

This early termination is important because once any diagonal violates the Toeplitz property, the entire matrix is invalid.

If all comparisons succeed, the function returns True after scanning the entire matrix.

Go Solution

func isToeplitzMatrix(matrix [][]int) bool {
    rows := len(matrix)
    cols := len(matrix[0])

    for row := 1; row < rows; row++ {
        for col := 1; col < cols; col++ {
            if matrix[row][col] != matrix[row-1][col-1] {
                return false
            }
        }
    }

    return true
}

The Go implementation follows the exact same logic as the Python version.

Go slices are used to represent the matrix. Since the problem guarantees a non-empty matrix, accessing matrix[0] is safe.

There are no integer overflow concerns because matrix values are very small. The solution uses only constant extra memory.

Worked Examples

Example 1

Input:

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

We begin scanning from row 1 and column 1.

Position	Current Value	Top-Left Value	Match?
(1,1)	1	1	Yes
(1,2)	2	2	Yes
(1,3)	3	3	Yes
(2,1)	5	5	Yes
(2,2)	1	1	Yes
(2,3)	2	2	Yes

All comparisons succeed, so the algorithm returns True.

Example 2

Input:

[
  [1, 2],
  [2, 2]
]

We begin scanning from (1,1).

Position	Current Value	Top-Left Value	Match?
(1,1)	2	1	No

Since the values differ, the algorithm immediately returns False.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m × n)	Every matrix cell is visited once
Space	O(1)	Only a few variables are used

The algorithm performs a constant-time comparison for each non-border cell in the matrix. Since there are approximately m × n cells, the overall time complexity is linear in the size of the matrix.

No additional data structures proportional to the input size are allocated, so the space complexity remains constant.

Test Cases

from typing import List

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

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

        return True

solution = Solution()

assert solution.isToeplitzMatrix(
    [[1, 2, 3, 4],
     [5, 1, 2, 3],
     [9, 5, 1, 2]]
) is True  # standard valid Toeplitz matrix

assert solution.isToeplitzMatrix(
    [[1, 2],
     [2, 2]]
) is False  # diagonal mismatch

assert solution.isToeplitzMatrix(
    [[5]]
) is True  # single element matrix

assert solution.isToeplitzMatrix(
    [[1, 2, 3]]
) is True  # single row matrix

assert solution.isToeplitzMatrix(
    [[1],
     [2],
     [3]]
) is True  # single column matrix

assert solution.isToeplitzMatrix(
    [[7, 7, 7],
     [7, 7, 7],
     [7, 7, 7]]
) is True  # all values identical

assert solution.isToeplitzMatrix(
    [[1, 2, 3],
     [4, 1, 9],
     [5, 4, 1]]
) is False  # one diagonal mismatch

assert solution.isToeplitzMatrix(
    [[1, 2],
     [3, 1],
     [4, 3],
     [5, 4]]
) is True  # rectangular matrix

assert solution.isToeplitzMatrix(
    [[1, 2],
     [3, 4]]
) is False  # smallest non-Toeplitz square matrix

Test	Why
Standard Toeplitz example	Verifies normal valid behavior
Simple invalid matrix	Confirms mismatch detection
Single element matrix	Tests minimum input size
Single row matrix	Ensures no unnecessary comparisons
Single column matrix	Ensures vertical edge case works
All identical values	Confirms repeated values are handled
One internal mismatch	Tests early failure logic
Rectangular matrix	Ensures non-square matrices work
Small invalid square matrix	Tests smallest failing square case

Edge Cases

A single row matrix is an important edge case because there are no diagonals containing more than one element. A naive implementation that assumes every element has a top-left neighbor could accidentally access invalid indices. This solution avoids that issue by starting iteration from row 1 and column 1.

A single column matrix behaves similarly. Every diagonal contains exactly one element, so the matrix is automatically Toeplitz. Since the inner loop starts at column 1, no invalid comparisons occur.

Another important edge case is a matrix where only one comparison fails late in the traversal. For example:

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

The mismatch occurs at the final comparison. The implementation correctly scans every required cell and immediately returns False when the violation is detected.

Rectangular matrices can also cause bugs if an implementation assumes equal numbers of rows and columns. This solution independently tracks row and column dimensions, so both wide and tall matrices are handled correctly.