Toeplitz Matrix: Diagonal Consistency Check

You are given an m x n matrix, and you need to determine whether it is a Toeplitz matrix. A matrix is Toeplitz if every diagonal from top-left to bottom-right contains the same element. This is LeetCode 766: Toeplitz Matrix.

For example, [[1,2,3,4],[5,1,2,3],[9,5,1,2]] is Toeplitz because each diagonal has a single repeated value: the main diagonal is all 1s, the diagonal above it is all 2s, and so on. But [[1,2],[2,2]] is not Toeplitz because the main diagonal contains both 1 and 2.

The constraint boils down to a simple local check: for every cell that has a top-left neighbor, that cell must equal its neighbor. If any pair disagrees, the answer is False.

The approach

A Toeplitz matrix has the property that matrix[i][j] == matrix[i-1][j-1] for all valid i and j. Two cells on the same diagonal always differ by the same offset in both row and column. So if you verify every adjacent pair along each diagonal, you have verified the entire diagonal.

That means you can skip row 0 and column 0 entirely (they have no top-left neighbor to compare against). You loop from row 1 to m-1 and from column 1 to n-1. For each cell, you compare it to the cell one step up and one step left. If any pair does not match, return False. If every pair matches, return True.

No need to trace full diagonals or build auxiliary structures. One nested loop with a single comparison per cell is enough.

Visual walkthrough

Let's walk through a 3x3 Toeplitz matrix step by step, checking each cell against its top-left neighbor.

Each step is a constant-time comparison. The entire walkthrough covers (m-1) * (n-1) cells, which for a 3x3 matrix is just 4 checks.

Python solution

def isToeplitzMatrix(matrix):
    rows, cols = len(matrix), len(matrix[0])
    for i in range(1, rows):
        for j in range(1, cols):
            if matrix[i][j] != matrix[i - 1][j - 1]:
                return False
    return True

1. Get the matrix dimensions rows and cols.
2. Loop i from 1 to rows - 1 and j from 1 to cols - 1, skipping the first row and first column since those cells have no top-left neighbor.
3. For each cell (i, j), compare it to (i-1, j-1). If they differ, the matrix is not Toeplitz, so return False immediately.
4. If the loop completes without finding a mismatch, return True.

Complexity analysis

Time: O(m * n) You visit every cell in the matrix at most once. Each visit does a single comparison in O(1) time.

Space: O(1) No extra data structures are allocated. You only use a few loop variables.

This is optimal. You must read every cell at least once to confirm the matrix is Toeplitz, so O(m * n) time is a lower bound.

Building blocks

Diagonal indexing in a matrix

Every cell (i, j) belongs to diagonal j - i. Cells sharing the same j - i value lie on the same top-left-to-bottom-right diagonal. This indexing scheme appears in many matrix problems, including N-Queens where you track occupied diagonals using row - col and row + col.

Neighbor comparison pattern

Instead of grouping elements and checking equality within each group, you compare each element to just one neighbor. This local-check approach works whenever the property you are verifying is transitive. You will see the same idea in problems that ask you to verify sorted order or check that adjacent elements satisfy some constraint.

Edge cases

Single row: a matrix with one row like [[1,2,3]] has no cells to compare (the inner loop never runs), so it is trivially Toeplitz. Return True.

Single column: a matrix with one column like [[1],[2],[3]] also has no cells with a top-left neighbor. Return True.

1x1 matrix: [[5]] is Toeplitz by definition. The loop body never executes.

All elements identical: [[7,7],[7,7]] is Toeplitz because every comparison trivially passes.

From understanding to recall

The insight here is easy to grasp: just compare each cell to its top-left neighbor. But during an interview, you might second-guess which neighbor to check (top-left? top-right?) or whether you need to handle diagonals explicitly. Drilling this problem with spaced repetition locks in the pattern so you write the two-line inner loop without hesitation. You see "Toeplitz" and immediately think matrix[i][j] != matrix[i-1][j-1], starting your loops at index 1.

Related posts

• Set Matrix Zeroes - Another matrix problem that uses in-place marking and careful row/column indexing
• Spiral Matrix - Layer-by-layer traversal of a 2D grid, building fluency with matrix coordinates
• Reshape the Matrix - Row-major index mapping between matrix shapes, a different take on 2D indexing