Toeplitz Matrix

Difficulty Level Easy
Frequently asked in Facebook
Array MatrixViews 3592

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,

Toeplitz Matrix

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.

References

Translate »