Toeplitz Matrix

766.Toeplitz Matrix

Array

Matrix

Problem Statement:

Given an m x n matrix, return true if the matrix is Toeplitz. A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same elements.

Example:

Input:

matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]

→

Output:

true

Java Solution:

// Don't over think. 
// Very normal traveral and verifying diagnol is same
// (You're not doing each diagnol separarelty)
public boolean isToeplitzMatrix(int[][] matrix) {
    // Check each element with its diagonal neighbor
    for (int i = 0; i < matrix.length - 1; i++) 
        for (int j = 0; j < matrix[i].length - 1; j++) 
            if (matrix[i][j] != matrix[i + 1][j + 1]) return false;
        
    return true;
}

Python Solution:

def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
    for i in range(len(matrix) - 1):
        for j in range(len(matrix[0]) - 1):
            if matrix[i][j] != matrix[i + 1][j + 1]:
                return False
    return True

C++ Solution:

class Solution {
public:
    bool isToeplitzMatrix(vectorint>>& matrix) {
        for(int i = 0; i < matrix.size() - 1; i++) {
            for(int j = 0; j < matrix[0].size() - 1; j++) {
                if(matrix[i][j] != matrix[i + 1][j + 1]) {
                    return false;
                }
            }
        }
        return true;
    }
};

Complexity:

Time: O(M×N) | Space: O(1)