Toeplitz Matrix or Not

Given a square matrix mat[][] of order n, check if it is a Toeplitz Matrix.

Note: A Toeplitz matrix - also called a diagonal-constant matrix - is a matrix where elements of every individual descending diagonal are same from left to right. Equivalently, for any entry mat[i][j], it is same as mat[i-1][j-1] or mat[i-2][j-2] and son on. We can get a better idea using the following image, all same colored cells should have same values.

Examples:

Input: mat[][] = [ [6, 7, 8],
[4, 6, 7]
[1, 4, 6] ]
Output: Yes
Explanation: All the diagonals of the given matrix are [6, 6, 6], [7, 7], [8], [4, 4], [1]. For every diagonal, as all the elements are same, the given matrix is Toeplitz Matrix.

Input: mat[][] = [ [6, 3, 8],
[4, 9, 7]
[1, 4, 6] ]
Output: No
Explanation: The primary diagonal elements of the given matrix are [6, 9, 6]. As the diagonal elements are not same, the given matrix is not Toeplitz Matrix.

[Expected Approach - 1] - Checking Each Diagonal - O(n × n) Time and O(1) Space

The idea is to traverse every downward-sloping diagonal in the matrix by using each element in the first row and each element in the first column as a starting point, and verify that every element along that diagonal matches the value at its head.

Follow the below given steps:

• Let n = mat.size() and m = mat[0].size().
• For each column index i from 0 to m - 1, call checkDiagonal(mat, 0, i); if it returns false, immediately return false from isToeplitz.
• For each row index i from 0 to n - 1, call checkDiagonal(mat, i, 0); if it returns false, immediately return false from isToeplitz.
• If all calls to checkDiagonal succeed, return true.
• In checkDiagonal(mat, x, y), compare mat[i][j] to mat[x][y] for each i = x+1, j = y+1 while i < n && j < m; return false on the first mismatch, otherwise return true after reaching the edge.

#include <iostream>
#include<vector>
using namespace std;

// function to check if diagonal elements are same
bool checkDiagonal(vector<vector<int>> &mat, int x, int y) {
    int n = mat.size(), m = mat[0].size();

    for(int i = x + 1, j = y + 1; 
            i < n && j < m; i++, j++) {
        if(mat[i][j] != mat[x][y])
            return false;
    }
    return true;
}

// Function to check whether given
// matrix is toeplitz matrix or not
bool isToeplitz(vector<vector<int>> &mat) {
    int n = mat.size(), m = mat[0].size();

    // check each descending diagonal starting from
    // first row and first column of the matrix
    for(int i = 0; i < m; i++)
        if(!checkDiagonal(mat, 0, i))
            return false;

    for(int i = 0; i < n; i++) 
        if(!checkDiagonal(mat, i, 0))
            return false;
    
    return true;
}

int main() {
    vector<vector<int>> mat = {
        {6, 7, 8},
        {4, 6, 7},
        {1, 4, 6}
    };
    if(isToeplitz(mat)) {
        cout << "Yes";
    } else {
        cout << "No";
    }
    return 0;
}

import java.util.List;
import java.util.Arrays;

class GfG {

    // function to check if diagonal elements are same
    static boolean checkDiagonal(List<List<Integer>> mat, int x, int y) {
        int n = mat.size(), m = mat.get(0).size();

        for(int i = x + 1, j = y + 1; 
                i < n && j < m; i++, j++) {
            if(!mat.get(i).get(j).equals(mat.get(x).get(y)))
                return false;
        }
        return true;
    }

    // Function to check whether given
    // matrix is toeplitz matrix or not
    static boolean isToeplitz(List<List<Integer>> mat) {
        int n = mat.size(), m = mat.get(0).size();

        // check each descending diagonal starting from
        // first row and first column of the matrix

        for(int i = 0; i < m; i++)
            if(!checkDiagonal(mat, 0, i))
                return false;

        for(int i = 0; i < n; i++) 
            if(!checkDiagonal(mat, i, 0))
                return false;

        // if all diagonals are same, return true
        return true;
    }

    public static void main(String[] args) {
        List<List<Integer>> mat = Arrays.asList(
            Arrays.asList(6, 7, 8),
            Arrays.asList(4, 6, 7),
            Arrays.asList(1, 4, 6)
        );
        if(isToeplitz(mat)) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

# function to check if diagonal elements are same
def checkDiagonal(mat, x, y):
    n, m = len(mat), len(mat[0])

    i, j = x + 1, y + 1
    while i < n and j < m:
        if mat[i][j] != mat[x][y]:
            return False
        i += 1
        j += 1
    return True

# Function to check whether given
# matrix is toeplitz matrix or not
def isToeplitz(mat):
    n, m = len(mat), len(mat[0])

    # check each descending diagonal starting from
    # first row and first column of the matrix

    for i in range(m):
        if not checkDiagonal(mat, 0, i):
            return False

    for i in range(n):
        if not checkDiagonal(mat, i, 0):
            return False

    return True

if __name__ == "__main__":
    mat = [
        [6, 7, 8],
        [4, 6, 7],
        [1, 4, 6]
    ]
    if isToeplitz(mat):
        print("Yes")
    else:
        print("No")

using System;
using System.Collections.Generic;

class GfG {

    // function to check if diagonal elements are same
    static bool checkDiagonal(List<List<int>> mat, int x, int y) {
        int n = mat.Count, m = mat[0].Count;

        for(int i = x + 1, j = y + 1; 
                i < n && j < m; i++, j++) {
            if(mat[i][j] != mat[x][y])
                return false;
        }
        return true;
    }

    // Function to check whether given
    // matrix is toeplitz matrix or not
    static bool isToeplitz(List<List<int>> mat) {
        int n = mat.Count, m = mat[0].Count;

        // check each descending diagonal starting from
        // first row and first column of the matrix

        for(int i = 0; i < m; i++)
            if(!checkDiagonal(mat, 0, i))
                return false;

        for(int i = 0; i < n; i++) 
            if(!checkDiagonal(mat, i, 0))
                return false;

        // if all diagonals are same, return true
        return true;
    }

    static void Main() {
        var mat = new List<List<int>> {
            new List<int> {6, 7, 8},
            new List<int> {4, 6, 7},
            new List<int> {1, 4, 6}
        };
        if(isToeplitz(mat)) {
            Console.WriteLine("Yes");
        } else {
            Console.WriteLine("No");
        }
    }
}

// function to check if diagonal elements are same
function checkDiagonal(mat, x, y) {
    let n = mat.length, m = mat[0].length;

    for(let i = x + 1, j = y + 1; 
            i < n && j < m; i++, j++) {
        if(mat[i][j] !== mat[x][y])
            return false;
    }
    return true;
}

// Function to check whether given
// matrix is toeplitz matrix or not
function isToeplitz(mat) {
    let n = mat.length, m = mat[0].length;

    // check each descending diagonal starting from
    // first row and first column of the matrix

    for(let i = 0; i < m; i++)
        if(!checkDiagonal(mat, 0, i))
            return false;

    for(let i = 0; i < n; i++) 
        if(!checkDiagonal(mat, i, 0))
            return false;

    return true;
}

// Driver code
let mat = [
    [6, 7, 8],
    [4, 6, 7],
    [1, 4, 6]
];
if(isToeplitz(mat)) {
    console.log("Yes");
} else {
    console.log("No");
}

Yes

[Expected Approach - 2] - Checking Diagonally Above Element - O(n × n) Time and O(1) Space

The core idea is to examine each cell, starting from the second row and second column. We compare each cell's value with its top-left neighbor. If a mismatch is found, the matrix is not Toeplitz, and we can stop. If the entire matrix is checked without any mismatches, all diagonals are constant.

Follow the below given steps:

• Let n = mat.size() and m = mat[0].size().
• Iterate i from 1 to n - 1 and within that j from 1 to m - 1.
• If mat[i][j] != mat[i - 1][j - 1] at any point, return false.
• Once all pairs have been checked with no mismatches, return true.

#include <iostream>
#include<vector>
using namespace std;

// Function to check whether given
// matrix is toeplitz matrix or not
bool isToeplitz(vector<vector<int>> &mat) {
    int n = mat.size(), m = mat[0].size();

    // check diagonally above element of
    // each element in the matrix
    for(int i = 1; i < n; i++) {
        for(int j = 1; j < m; j++) {
            if(mat[i][j] != mat[i - 1][j - 1])
                return false;
        }
    }
    
    return true;
}

int main() {
    vector<vector<int>> mat = {
        {6, 7, 8},
        {4, 6, 7},
        {1, 4, 6}
    };
    if(isToeplitz(mat)) {
        cout << "Yes";
    } else {
        cout << "No";
    }
    return 0;
}

import java.util.List;
import java.util.Arrays;

class GfG {

    // Function to check whether given
    // matrix is toeplitz matrix or not
    static boolean isToeplitz(List<List<Integer>> mat) {
        int n = mat.size(), m = mat.get(0).size();

        // check diagonally above element of
        // each element in the matrix
        for(int i = 1; i < n; i++) {
            for(int j = 1; j < m; j++) {
                if(mat.get(i).get(j) != mat.get(i - 1).get(j - 1))
                    return false;
            }
        }
        
        return true;
    }

    public static void main(String[] args) {
        List<List<Integer>> mat = Arrays.asList(
            Arrays.asList(6, 7, 8),
            Arrays.asList(4, 6, 7),
            Arrays.asList(1, 4, 6)
        );
        if(isToeplitz(mat)) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

# Function to check whether given
# matrix is toeplitz matrix or not
def isToeplitz(mat):
    n, m = len(mat), len(mat[0])

    # check diagonally above element of
    # each element in the matrix
    for i in range(1, n):
        for j in range(1, m):
            if mat[i][j] != mat[i - 1][j - 1]:
                return False

    # if all diagonals are same, return true
    return True

if __name__ == "__main__"
mat = [
    [6, 7, 8],
    [4, 6, 7],
    [1, 4, 6]
]
if isToeplitz(mat):
    print("Yes")
else:
    print("No")

using System;
using System.Collections.Generic;

class GfG {

    // Function to check whether given
    // matrix is toeplitz matrix or not
    static bool isToeplitz(List<List<int>> mat) {
        int n = mat.Count, m = mat[0].Count;

        // check diagonally above element of
        // each element in the matrix
        for(int i = 1; i < n; i++) {
            for(int j = 1; j < m; j++) {
                if(mat[i][j] != mat[i - 1][j - 1])
                    return false;
            }
        }
        
        // if all diagonals are same, return true
        return true;
    }

    static void Main() {
        var mat = new List<List<int>> {
            new List<int> {6, 7, 8},
            new List<int> {4, 6, 7},
            new List<int> {1, 4, 6}
        };
        if(isToeplitz(mat)) {
            Console.WriteLine("Yes");
        } else {
            Console.WriteLine("No");
        }
    }
}

// Function to check whether given
// matrix is toeplitz matrix or not
function isToeplitz(mat) {
    let n = mat.length, m = mat[0].length;

    // check diagonally above element of
    // each element in the matrix
    for(let i = 1; i < n; i++) {
        for(let j = 1; j < m; j++) {
            if(mat[i][j] !== mat[i - 1][j - 1])
                return false;
        }
    }
    
    return true;
}


// Driver code
let mat = [
    [6, 7, 8],
    [4, 6, 7],
    [1, 4, 6]
];
if(isToeplitz(mat)) {
    console.log("Yes");
} else {
    console.log("No");
}

Yes