Given a 2-D matrix of size (m x n), check whether the matrix is Toeplitz or not. A Toeplitz matrix is a matrix in which the elements on the same diagonal from top left to bottom left are the same for all the diagonals.
Table of Contents
Examples
Input
1 2 3 4
5 1 2 3
9 5 1 2
Output
true
Explanation
The diagonals are [“1”, “1”, “1”], [“2”, “2”, “2”], [“3”, “3”], [“4”], [“5”, “5”], [“9”]
In every diagonal, all the elements are the same so the matrix is Toeplitz.
Input
1 2
2 2
Output
false
Explanation
Dialgonals are [“1”, “2”], [“2”], [“2”]
The diagonal [“1”, “2”] has different elements, so the matrix is not toeplitz.
Algorithm for check Toeplitz Matrix
Traverse all the diagonals one by one and if all the elements are not the same for any diagonal, the matrix is not Toeplitz, else it is Toeplitz.
Diagonals are to be traversed as shown in image below,
The starting points of diagonals are, [0, 0], [0, 1], [0, 2], [0, 3], [1, 0], [2, 0] for above example.
Either the column or row is 0 in the starting points, traverse every diagonal by starting from the starting point and increasing the value of row and column by 1.
Explanation for Toeplitz Matrix
Consider the example,
1 2 3 4
5 1 2 3
9 5 1 2
Traverse all the diagonals with the starting point in the zeroth row.
Diagonal 1 : Starting Point= (0, 0)
Elements = {1, 1, 1}
All the elements are the same, so continue.
Diagonal 2 : Starting Point = (0, 1)
Elements = {2, 2, 2}
All the elements are the same, so continue.
Diagonal 3 : Starting Point = (0, 2)
Elements = {3, 3, 3}
All the elements are the same, so continue.
Diagonal 4 : Starting Point= (0, 3)
Elements = {4}
All the elements are the same, so continue.
Traverse all the diagonals with the starting point in the zeroth column.
Diagonal 1 : Starting Point =(0, 0)
Elements = {1, 1, 1}
All the elements are the same, so continue.
Diagonal 2 : Starting Point =(1, 0)
Elements = {5, 5}
All the elements are the same, so continue.
Diagonal 3 : Starting Point =(2, 0)
Elements = {9}
All the elements are the same, so continue.
All the diagonals have the same element, so the given matrix is Toeplitz.
JAVA Code for Toeplitz Matrix
public class ToeplitzMatrix {
private static boolean isToeplitz(int[][] matrix) {
boolean ans = true;
int n = matrix.length;
int m = matrix[0].length;
// First row diagonals
for (int i = 0; i < m; i++) {
int x = 0, y = i;
int curr = matrix[x][y];
x++; y++;
while (x < n && y < m) {
// If any element is not same, this can't be a toeplitz matrix
if (matrix[x][y] != curr) {
ans = false;
break;
}
// Increment row and column by 1
x++; y++;
}
if (!ans)
break;
}
// First column diagonals
for (int i = 1; i < n; i++) {
int x = i, y = 0;
int curr = matrix[x][y];
x++; y++;
while (x < n && y < m) {
// If any element is not same, this can't be a toeplitz matrix
if (matrix[x][y] != curr) {
ans = false;
break;
}
// Increment row and column by 1
x++; y++;
}
if (!ans)
break;
}
return ans;
}
public static void main(String[] args) {
// Example 1
int[][] matrix = new int[][] {
{1, 2, 3, 4},
{5, 1, 2, 3},
{9, 5, 1, 2}};
System.out.println(isToeplitz(matrix));
// Example 2
int[][] matrix2 = new int[][] {
{1, 2},
{2, 2}
};
System.out.println(isToeplitz(matrix2));
}
}C++ Code for Toeplitz Matrix
#include<bits/stdc++.h>
using namespace std;
int matrix[4][4];
bool isToeplitz(int n, int m) {
bool ans = true;
// First row diagonals
for (int i = 0; i < m; i++) {
int x = 0, y = i;
int curr = matrix[x][y];
x++; y++;
while (x < n && y < m) {
// If any element is not same, this can't be a toeplitz matrix
if (matrix[x][y] != curr) {
ans = false;
break;
}
// Increment row and column by 1
x++; y++;
}
if (!ans)
break;
}
// First column diagonals
for (int i = 1; i < n; i++) {
int x = i, y = 0;
int curr = matrix[x][y];
x++; y++;
while (x < n && y < m) {
// If any element is not same, this can't be a toeplitz matrix
if (matrix[x][y] != curr) {
ans = false;
break;
}
// Increment row and column by 1
x++; y++;
}
if (!ans)
break;
}
return ans;
}
int main() {
// Example 1
matrix[0][0] = 1;
matrix[0][1] = 2;
matrix[0][2] = 3;
matrix[0][3] = 4;
matrix[1][0] = 5;
matrix[1][1] = 1;
matrix[1][2] = 2;
matrix[1][3] = 3;
matrix[2][0] = 9;
matrix[2][1] = 5;
matrix[2][2] = 1;
matrix[2][3] = 2;
if (isToeplitz(3, 4)) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
// Example 2
matrix[0][0] = 1;
matrix[0][1] = 2;
matrix[1][0] = 2;
matrix[1][1] = 2;
if (isToeplitz(2, 2)) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
return 0;
}true false
Complexity Analysis
Time Complexity = O(m * n)
Space Complexity = O(1)
where m and n are the number of rows and columns in the 2D matrix.