Toeplitz Matrix
Problem
A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same value. Return whether the given matrix is Toeplitz.
matrix=[[1,2,3,4],[5,1,2,3],[9,5,1,2]]truedef 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 Truefunction isToeplitzMatrix(matrix) {
for (let i = 1; i < matrix.length; i++)
for (let j = 1; j < matrix[0].length; j++)
if (matrix[i][j] !== matrix[i-1][j-1]) return false;
return true;
}boolean isToeplitzMatrix(int[][] matrix) {
for (int i = 1; i < matrix.length; i++)
for (int j = 1; j < matrix[0].length; j++)
if (matrix[i][j] != matrix[i-1][j-1]) return false;
return true;
}bool isToeplitzMatrix(vector<vector<int>>& matrix) {
for (int i = 1; i < (int)matrix.size(); i++)
for (int j = 1; j < (int)matrix[0].size(); j++)
if (matrix[i][j] != matrix[i-1][j-1]) return false;
return true;
}Explanation
A matrix is Toeplitz when every diagonal running top-left to bottom-right holds a single repeated value. The neat insight is that we do not need to trace whole diagonals — we only need each cell to equal the cell diagonally above-left of it.
Two cells matrix[i][j] and matrix[i-1][j-1] sit on the same diagonal. If every such neighboring pair matches, then by transitivity the entire diagonal is constant.
So we loop over every cell starting from row 1 and column 1 (cells in the first row or first column have no upper-left neighbor) and check matrix[i][j] != matrix[i-1][j-1]. The instant we find a mismatch we return false; if we get through all cells, we return true.
Example: [[1,2,3,4],[5,1,2,3],[9,5,1,2]]. Cell matrix[1][1]=1 equals matrix[0][0]=1, matrix[1][2]=2 equals matrix[0][1]=2, and so on for every inner cell, so the answer is true.