# Toeplitz Matrix  Difficulty Level Easy
Array Matrix

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.

## 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.

K-th Smallest Element in a Sorted Matrix

## 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.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;

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 = 1;
matrix = 2;
matrix = 3;
matrix = 4;
matrix = 5;
matrix = 1;
matrix = 2;
matrix = 3;
matrix = 9;
matrix = 5;
matrix = 1;
matrix = 2;
if (isToeplitz(3, 4)) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}

// Example 2
matrix = 1;
matrix = 2;
matrix = 2;
matrix = 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. 