766. Toeplitz Matrix

The Toeplitz Matrix problem is a common LeetCode interview question that evaluates pattern recognition and efficient matrix traversal. It has frequently shown up in interviews at Google and Meta (Facebook). Interviewers use it to test whether candidates can reduce unnecessary space usage while handling edge cases correctly. Solving this problem builds strong fundamentals for many matrix-based interview questions.

Problem statement

You are given an m x n matrix. Return TRUE if the matrix is Toeplitz, otherwise return FALSE.

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 20
• 0 <= matrix[i][j] <= 99

Examples

Naive approach

One of the initial ideas is to collect each diagonal into a list (or a hash map) and then check whether all values inside each diagonal are the same. A convenient way to identify diagonals is using (r – c) as a key, where r is the row index and c is the column index. This is because every cell on the same top-left to bottom-right diagonal shares the same (r – c) value. After building these groups, we verify if each list contains identical values.

As we iterate through the matrix, each element matrix[r][c] is added to a group associated with the key (r – c).

This step only determines which elements belong to the same diagonal; it does not check whether the diagonal is valid.

Once the groups are formed, we validate each diagonal by comparing all values in the group against the first value. If any value differs, the matrix is not Toeplitz. In the example below, diagonal 0 contains values [1, 1, 9], which are not all the same, so the matrix is not Toeplitz.

This naive approach works, but in the worst case, the hash map can end up storing almost all elements of the matrix across the diagonal lists leading to a space complexity of O(m x n), where m is the number of rows and n is the number of columns.

Key observation

We don’t actually need to store entire diagonals to solve this problem. A Toeplitz matrix follows a very simple rule: every element must match the element one step up-left.

That means for every cell (r, c) where r > 0 and c > 0, we only need to check: matrix[r][c] == matrix[r – 1][c – 1]

If this condition holds for every valid cell, then every diagonal automatically contains the same value, so the matrix is Toeplitz. If even one comparison fails, we can immediately say the matrix is not Toeplitz.

This is helpful because we compare each cell only once, we don’t use any extra memory to store diagonals, and the solution stays very clean.

Optimized solution

We scan the matrix in a simple, systematic way: row by row and left to right. The first row and the first column are skipped because those cells do not have a valid top-left neighbor. A cell needs both r > 0 and c > 0 for (r – 1, c – 1) to exist.

Once we start from the second row and second column, every cell we visit belongs to some diagonal, and comparing it to its top-left neighbor is basically checking whether its diagonal is staying consistent. If it follows the Toeplitz rule, then the current diagonal is still following it at that point, so we continue scanning. If we ever find a cell where it’s not the case, that means the diagonal has two different values, so the matrix cannot be Toeplitz, and we can immediately return FALSE without checking anything else. If we reach the end of the scan and every comparison matches, then every diagonal must have remained consistent, so we return TRUE.

Step-by-step algorithm

1. Compute the number of rows and columns as m = len(matrix) and n = len(matrix[0]).
2. Iterate over the matrix starting from the second row and second column. For each row r (starting from 1) and its c (starting from 1):
   1. Compare the current cell with its top-left neighbor. If they are not equal, i.e., matrix[r][c] != matrix[r - 1][c - 1], return FALSE.
3. Once the entire matrix has been traversed, return TRUE.

1 / 3

Python implementation for the optimal solution

Now, let’s take a look at the code that implements this solution:

def isToeplitzMatrix(matrix):
    # Number of rows
    m = len(matrix)

    # Number of columns
    n = len(matrix[0])

    # Start from row 1 and col 1 because (0,*) and (*,0) have no top-left neighbor
    for r in range(1, m):
        for c in range(1, n):
            # Compare current cell with its top-left neighbor
            if matrix[r][c] != matrix[r - 1][c - 1]:
                # If any diagonal mismatch happens, it's not Toeplitz
                return False

    # All diagonal comparisons matched
    return True


# Driver code
def main():
    test_cases = [
        ([[5]]),
        ([[1, 2, 3],
          [4, 1, 2],
          [5, 4, 1]]),
        ([[1, 2, 3],
          [4, 9, 2],
          [5, 4, 1]]),
        ([[7, 7, 7, 7],
          [8, 7, 7, 7]]),
        ([[0, 1, 2],
          [3, 0, 9]]),
    ]

    for i, (matrix) in enumerate(test_cases, 1):
        result = isToeplitzMatrix(matrix)
        print(f"{i}.\tmatrix =\n\t" + "\n\t".join(str(row) for row in matrix))
        print(f"\n\tOutput: {result}")
        print("-" * 75)

if __name__ == "__main__":
    main()

Time complexity

We scan through the matrix once, comparing each cell (except those in the first row and first column) with its top-left neighbor. Therefore, the time complexity is O(m x n).

Space complexity

The algorithm only uses a few variables such as m, n, and the loop counters. It does not create any extra data structure that grows with the size of the matrix. So, the extra space used is constant, which means the space complexity is O(1).

Common mistakes to avoid and interview tips

This problem looks straightforward, but small details matter a lot in interviews. Here are some common mistakes to avoid, along with useful interview tips.

• Checking the wrong neighbor: Toeplitz uses the top-left neighbor (r-1, c-1), not top (r-1, c) or left (r, c-1).
• Forgetting to skip row 0 or column 0: Those don’t have a top-left neighbor, so you must start loops from 1.
• Returning TRUE too early: Don’t return TRUE after a single diagonal match. You must validate all required cells.
• Many interviewers ask follow-ups like:
  • “What if the matrix is too big to fit in memory?”
  • “What if rows arrive as a stream (one row at a time)?”
• A common follow-up approach: For streaming rows, you only need to store the previous row, then compare current row[c] with previous row[c-1].