Toeplitz Matrix - Leetcode Solution

Problem:

Given a matrix of integers matrix, return true if it is a Toeplitz matrix. Otherwise, return false.

A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same element.

Example 1: Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]] Output: true Explanation: In the first diagonal the elements are [1], [5, 2], [9, 1, 3], [4, 2], [3] and in all of them the elements are the same. Thus the matrix is a Toeplitz matrix.

Example 2: Input: matrix = [[1,2],[2,2]] Output: false Explanation: The diagonal [1, 2] has different elements.

Constraints: 1 <= matrix.length <= 20 1 <= matrix[i].length <= 20 0 <= matrix[i][j] <= 99

Solution:

The problem is to check if all diagonals from left to right in a given matrix have the same elements. A matrix with only one element is a Toeplitz matrix by definition. For matrices with size greater than one, we can check if every element is the same as the element in the diagonal one above and one to the left of it.

We can implement this solution by iterating over the matrix, checking all elements except the first row and the first column. For each element, we check if it is equal to the element above and to the left of it. If it is not, we return false. If we reach the end of the matrix without returning false, we return true.

Here is the Python code for our solution:

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

In the code, we use two nested loops to iterate over the matrix. We start at row 1 and column 1 (since we don’t need to check the first row and the first column). For each element, we check if it is equal to the element one above and one to the left of it. If it is not, we return false. If we reach the end of the matrix without returning false, we return true.

This solution has a time complexity of O(m*n) where m and n are the size of the input matrix. The space complexity is O(1), as we do not use any data structure to store the elements.

1