Given an m x n matrix, return&nbsp;true&nbsp;if the matrix is Toeplitz. Otherwise, return false.

A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same elements.

&nbsp;
Example 1:

Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Output: true
Explanation:
In the above grid, the&nbsp;diagonals are:
"[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]".
In each diagonal all elements are the same, so the answer is True.


Example 2:

Input: matrix = [[1,2],[2,2]]
Output: false
Explanation:
The diagonal "[1, 2]" has different elements.


&nbsp;
Constraints:


	m == matrix.length
	n == matrix[i].length
	1 &lt;= m, n &lt;= 20
	0 &lt;= matrix[i][j] &lt;= 99


&nbsp;
Follow up:


	What if the matrix is stored on disk, and the memory is limited such that you can only load at most one row of the matrix into the memory at once?
	What if the matrix is so large that you can only load up a partial row into the memory at once?


###########################################################################################
#       Number of rows(M) x expected numbers(N)
#   Space: O(N)
#       We need to store the expected numbers in list
############################################################################################
class Solution:
    def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
        # Validate Input
        if not matrix or not matrix[0]:
            return False                
        
        # Create a deque tracking the expected values for the next row
        expected = matrix[0]
        # We only care about the elements before last element
        expected.pop()
        
        # From the second row, pop out the last element of the expected numbers and compare it with the target row[1:]
        for row in matrix[1:]:
            # Compare row with expected numbers, invalidate it as soon as we find the numbers are not the same (O(N))
            if row[1:] != expected:
                return False
            else:
                # Pop the last element from row, use it as the expected numbers for the next iteration
                row.pop()
                expected = row
        # If we've reached here, all diagonals aligned
        return True
class Solution {
    public boolean isToeplitzMatrix(int[][] matrix) {
          
        
        int n = matrix.length;
        int m = matrix[0].length;
        
        for(int i = 0; i < m; i++){
            int row = 0;
            int col = i;
            int e = matrix[row++][col++];
           while(row < n && col< m){
               if(e == matrix[row][col]){
                   row++;
                   col++;
               }else{
                   return false;
               }
           }  
        }
        
        for(int r = 1; r < n; r++){
            int row = r;
            int col = 0;
            int e =matrix[row++][col++];
            while(row < n && col < m){
                if(e == matrix[row][col]){
                    row++;
                    col++;
                }else{
                    return false;
                }
            }
        }
        
        return true;
    }
}
class Solution {
public:
    bool isToeplitzMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                if (matrix[i][j] != matrix[i - 1][j - 1])
                    return false;
        return true;
    }
};
var isToeplitzMatrix = function(matrix) {
    for (let i=0; i < matrix.length-1; i++) {
        for (let j=0; j < matrix[i].length-1; j++) {
            if (matrix[i][j] !== matrix[i+1][j+1]) {
                return false
            }
        }
    }

    return true
};
Toeplitz Matrix