Toeplitz Matrix  

Difficulty Level Easy
Frequently asked in Facebook
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,

Please click Like if you loved this article?

Toeplitz MatrixPin

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.

See also
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[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.

Please click Like if you loved this article?

See also
Subtract the Product and Sum of Digits of an Integer Leetcode Solution

References

Please click Like if you loved this article?

Ads Blocker Image Powered by Code Help Pro
Ads Blocker Detected!!!

This website does not work properly with AdBlock. We have detected that you are using extensions to block ads. Please disable Adblocker to view the content.

Refresh